Нелинейные уравнения можно разделить на 2 класса - алгебраические и трансцендентные. Алгебраическими уравнениями называют уравнения, содержащие только алгебраические функции (целые, рациональные, иррациональные). В частности, многочлен является целой алгебраической функцией. Уравнения, содержащие другие функции (тригонометрические, показательные, логарифмические и другие) называются трансцендентными.

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

1. точные методы
;
2. итерационные методы
.

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

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

Пусть дано уравнение

1. Функция f (x ) непрерывна на отрезке [a, b ] вместе со своими производными 1-го и 2-го порядка.
2. Значения f (x ) на концах отрезка имеют разные знаки (f (a ) * f (b ) < 0).
3. Первая и вторая производные f" (x ) и f"" (x ) сохраняют определенный знак на всем отрезке.

Условия 1) и 2) гарантируют, что на интервале [a, b ] находится хотя бы один корень, а из 3) следует, что f (x ) на данном интервале монотонна и поэтому корень будет единственным.

Решить уравнение (1) итерационным методом значит установить, имеет ли оно корни, сколько корней и найти значения корней с нужной точностью.

Всякое значение , обращающее функцию f (x ) в нуль, т.е. такое, что:

называется корнем уравнения (1) или нулем функции f (x ).

Задача нахождения корня уравнения f (x ) = 0 итерационным методом состоит из двух этапов:

1. отделение корней
- отыскание приближенного значения корня или содержащего его отрезка;
2. уточнение приближенных корней
- доведение их до заданной степени точности.

Процесс отделения корней начинается с установления знаков функции f (x ) в граничных x = a и x = b точках области ее существования.

Пример 1. Отделить корни уравнения:

f(x ) є x 3 - 6х + 2 = 0.

Составим приблизительную схему:

Следовательно, уравнение (2) имеет три действительных корня, лежащих в интервалах [-3, -1], и .

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

В инженерной практике распространен графический способ определения приближенных корней.

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

Уравнение (4) удобно переписать в виде равенства:

Отсюда ясно, что корни уравнения (4) могут быть найдены как абсциссы точек пересечения логарифмической кривой y = lg x и гиперболы y = . Построив эти кривые, приближенно найдем единственный корень уравнения (4) или определим его содержащий отрезок .

Итерационный процесс состоит в последовательном уточнении начального приближения х 0 . Каждый такой шаг называется итерацией . В результате итераций находится последовательность приближенных значений корня х 1 , х 2 , ..., х n . Если эти значения с увеличением числа итераций n приближаются к истинному значению корня, то говорят, что итерационный процесс сходится .

Для нахождения корня уравнения (1), принадлежащего отрезку [a, b ], делим этот отрезок пополам. Если f = 0 , то x = является корнем уравнения. Если f не равно 0 (что, практически, наиболее вероятно), то выбираем ту из половин или , на концах которой функция f (x ) имеет противоположные знаки. Новый суженный отрезок [ а 1 , b 1] снова делим пополам и производим те же самые действия.

Метод половинного деления практически удобно применять для грубого нахождения корня данного уравнения, метод прост и надежен, всегда сходится.

Пример 3. Методом половинного деления уточнить корень уравнения

f(x ) = x 4 + 2 x 3 - x - 1 = 0

лежащий на отрезке [ 0, 1] .

Последовательно имеем:

f(0) = - 1; f (1) = 1; f (0,5) = 0,06 + 0,25 - 0,5 - 1 = - 1,19;

f(0,75) = 0,32 + 0,84 - 0,75 - 1 = - 0,59;

f(0,875) = 0,59 + 1,34 - 0,88 - 1 = + 0,05;

f(0,8125) = 0,436 + 1,072 - 0,812 - 1 = - 0,304;

f(0,8438) = 0,507 + 1,202 - 0,844 - 1 = - 0,135;

f(0,8594) = 0,546 + 1,270 - 0,859 - 1 = - 0,043 и т. д.

Можно принять

x = (0,859 + 0,875) = 0,867

В данном методе процесс итераций состоит в том, что в качестве приближений к корню уравнения (1) принимаются значения х 1 , х 2 , ..., х n точек пересечения хорды АВ с осью абсцисс (Рисунок 3). Сначала запишем уравнение хорды AB :

.

Для точки пересечения хорды AB с осью абсцисс (х = х 1 , y = 0) получим уравнение:

Пусть для определенности f"" (x ) > 0 при а х b (случай f"" (x ) < 0 сводится к нашему, если записать уравнение в виде - f (x ) = 0). Тогда кривая у = f (x ) будет выпукла вниз и, следовательно, расположена ниже своей хорды АВ . Возможны два случая: 1) f (а ) > 0 (Рисунок 3, а ) и 2) f (b ) < 0 (Рисунок 3, б ).

Рисунок 3, а, б.

В первом случае конец а неподвижен и последовательные приближения: x 0 = b ;x , где функция f (х ) имеет знак, противоположный знаку ее второй производной f"" (х ).

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

| x i - x i - 1 |< e ,

где e - заданная предельная абсолютная погрешность.

Пример 4. Найти положительный корень уравнения

f(x ) = x 3 - 0,2 x 2 - 0,2 х - 1,2 = 0

с точностью e = 0,01.

Прежде всего, отделяем корень. Так как

f (1) = -0,6 < 0 и f (2) = 5,6 > 0,

то искомый корень x лежит в интервале . Полученный интервал велик, поэтому разделим его пополам. Так как

f (1,5) = 1,425 > 0, то 1< x < 1,5.

Так как f"" (x ) = 6 x - 0,4 > 0 при 1 < х < 1,5 и f (1,5) > 0, то воспользуемся формулой (5) для решения поставленной задачи:

= 1,15;

| x 1 - x 0 | = 0,15 > e ,

следовательно, продолжаем вычисления;

f (х 1) = -0,173;

= 1,190;

|x 2 - x 1 | = 0,04 > e ,

f (х 2) = -0,036;

= 1,198;

| x 3 - x 2 | = 0,008 < e .

Таким образом, можно принять x = 1,198 с точностью e = 0,01.

Заметим, что точный корень уравнения x = 1,2.

Иванов Иван

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

Разделим отрезок пополам точкой. Если (что практически наиболее вероятно), то возможны два случая: либо f(x) меняет знак на отрезке (Рис. 3.8), либо на отрезке (Рис. 3.9)

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

Пример 4. Уравнение 5x - 6x -3 = 0 имеет единственный корень на отрезке . Решить это уравнение методом половинного деления.

Решение : Программа на языке Паскаль может быть такой:

function f(x: real): real;

f:=exp(x*ln(5))-6*x-3;

a, b, e, c, x: real;

while abs(b-a)>e do

if f(a)*f(c)<0 then

writeln ("x=",x:3:3," f(x)=",f(x):4:4);

Результат выполнения программы:

e=0.001 x=1.562 f(x)=-0.0047

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

1.Определить новое приближение корня х в середине отрезка [а,b]: х=(а+b)/2.

2.Найти значения функции в точках а и х : F(a) и F(x) .

3.Проверить условие F(a)*F(x) < 0 . Если условие выполнено, то корень расположен на отрезке [а,х] b переместить в точку х (b=х) . Если условие не выполнено, то корень расположен на отрезке [х,b] . В этом случае необходимо точку а переместить в точку х (а=х) .

4.Перейти к пункту 1 и вновь поделить отрезок пополам. Алгоритм продолжить до того времени, пока не будет выполнено условие /F(x)/ < e (заданная точность).

21.Метод простой итерации для поиска корней. Геометрическая интерпретация .

Исходное уравнение f(x)=0 эквивалентными преобразованиями приводится к виду с выделением неизвестного в левой части, то есть x=φ(x),где φ(x) – некоторая функция, связанная с исходной функцией f(x). Такая форма записи уравнения позволяет, задаваясь начальным приближением x 0, получить следующее, первое приближение x 1 =φ(x 0), далее получают второе приближение x 2 =φ(x 1) и так далее x n +1 =φ(x n)…. Последовательность {x n }= x 0, x 1, x 2, …, x n ,… называется последовательностью итераций или приближений с начальным значением x 0. Если функция φ(x) на непрерывна и существует предел ξ = lim x n при n→∞, то, переходя к пределу в равенстве x n +1 =φ(x n), найдем, что при n→ ∞: lim x n +1 =lim φ(x n)=φ(lim x n), то есть ξ=φ(ξ).Следовательно, если последовательность приближений сходится, то она сходится к корню уравнения (2), а значит и уравнения (1). В силу сходимости итерационного процесса этот корень можно вычислить при достаточно большом n с любой заданной точностью. Однако необходимо определить при каких условиях последовательность {x n }будет сходящейся. Получим связь между погрешностями двух соседних приближений - ε n и ε n +1: x n =ξ+ε n , x n +1 =ξ+ε n +1. Подставим эти представления в x n +1 =φ(x n) и разложим функцию в ряд Тейлора в окрестности корня:ξ+ε n +1 =φ(ξ+ε n)=φ(ξ)+ε n φ’(ξ)+(ε n 2 /2!)φ’’(η), где η Î [ξ; ξ+ε n ] Ì .Поскольку ξ - корень, то ξ=φ(ξ) , то получаем: ε n +1 =ε n φ’(ξ)+(φ’’(η)/2)ε n 2 .Так как ε<1, то ε n 2 <<ε n . Поэтому если φ’(ξ) ¹ 0,то основной вклад в погрешность дает первое слагаемое, а слагаемым (φ’’(η)/2)ε n 2 можно пренебречь, то есть ε n +1 » ε n φ’(ξ).Это означает, что погрешность будет уменьшаться на каждом последующем шаге, если |φ’(ξ)|<1, тогда для любого n |ε n +1 |<|ε n |. Сформулируем теорему о сходимости метода простых итераций, дающую достаточные условия сходимости.

Теорема о сходимости метода простых итераций. Пусть ξ - корень уравнения x=φ(x), функция φ(x) определена и дифференцируема на отрезке , причем для x Î все значения функции φ (x) Î . Тогда, если существует такое положительное число q<1, что при x Î выполняется неравенство |φ’(ξ)|≤q<1, то на отрезке уравнение x=φ(x) имеет единственный корень x=ξ и процесс итераций, выраженный формулой x n +1 =φ(x n), где n=1,2,3… , сходится к этому корню независимо от выбора начального приближения x 0 Î .Таким образом, последовательность {x n },начинающаяся с любого x 0 Î , сходится к корню ξ со скоростью геометрической прогрессии, причем скорость сходимости тем выше, чем меньше величина q Î (1;0).Если функция φ(х) монотонно возрастает и 0<φ’(х)<1, то все приближения лежат по одну сторону от корня - такую сходимость называют монотонной (или ступенчатой) – рис.1. Если функция φ(х) монотонно убывает и 0>φ’(х)>-1, то соседние приближения лежат по разную сторону от корня – такую сходимость называют двусторонней (или спиралевидной) – рис.2. Поскольку в этом случае корень заключен в интервале, концами которого являются соседние приближения – ξÎ(x n ,x n +1), то выполнение условия |x n +1 -x n |<ε обеспечивает выполнение условия |ξ-x n +1 |<ε.

Чтобы можно было сравнивать итерационные методы по скорости сходимости, вводят следующие понятия:

Определение 1: Сходимость последовательности {x n } к ξ называется линейной (соответственно, итерационный процесс - линейно сходящимся ), если существует такая постоянная CÎ(0,1) и такой номер n 0 , что выполняются неравенства |ξ-x n +1 |≤C|ξ-x n | для n≥n 0.

Для введенных ранее погрешностей это означает |ε n+1 |≤C|ε n |. В методе простой итерации в роли постоянной C выступает значение q, то есть метод сходится линейно.

Определение 2: Последовательность приближений {x n } сходится к ξ по меньшей мере с р -ым порядком (соответственно, итерационный процесс имеет по меньшей мере p -ый порядок), если найдутся такие константы C>0, p ≥1 и n 0 , что для всех n≥n 0 выполняются условия |ξ-x n +1 |≤C|ξ-x n | р (или в других обозначениях |ε n+1 |≤C|ε n | p).

Двоичный поиск. Метод половинного деления.

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

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

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

Для учащихся предлагается данная теория, однако в более преемственной форме.

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

Предлагается игра “Угадай – ка”. Вот ее условия:

Учащиеся задумывают натуральное число от 1 до 16 (число записывают на листок и передают одноклассникам для ознакомления), а учитель задавая не более 4 вопросов, отгадывает задуманное число. При этом на вопросы учителя учащиеся отвечают только “да” или “нет”. Например, задумано число 15.

Происходит диалог следующего вида:

Учитель спрашивает: 1. Задуманное число больше 8? Ответ учеников : Да.

Учитель спрашивает: 2. Задуманное число больше 12? Ответ учеников : Да.

Учитель спрашивает: 3. Задуманное число больше 14? Ответ учеников : Да.

Учитель спрашивает: 4. Задуманное число больше 15? Ответ учеников : Нет.

Учитель отвечает : Это число 15.

Такую игру проигрывают 3 раза, тем самым убеждают учащихся, что совпадений нет, а есть точный алгоритм угадывания. Предлагается проанализировать следующие вопросы :

1. Как учитель угадывает задуманное число?

2. Почему гарантировано угадывание числа за 4 вопроса?

1. Тот промежуток чисел, в котором находится задуманное число, следует разделить пополам и выяснить в какой половине находится это число. С уменьшенным вдвое промежутком опять поступить так же, то есть, как сказали бы артиллеристы, взять искомое число в “вилку” до полного “попадания в цель”

Откуда же видно, что для этого достаточно четырёх вопросов?

2. Дело в том, что четырёхкратное деление пополам промежутка чисел от 1 до 16 приведёт к промежутку, состоящему только из двух чисел: 1 и 2. Удвоим его. Получим промежуток чисел от 1 до 4. Снова удвоим и так далее, пока верхняя граница не достигнет 2 4 =16, которая, как видите, включает наш промежуток. То есть мы должны брать ту степень числа 2, при которой наш промежуток будет полностью включаться, либо быть равным, либо меньшим.

Для лучшего восприятия посмотрите (рис.1), где красные линии – это ответ “Да”, черные – ответ “Нет”. При каждом делении промежутка на 2 существует верхняя граница N, которая звучит в вопросе: “Это число больше N ?”

Метод, который мы сейчас разобрали для отгадывания задуманного числа, называют двоичным поиском . Он применим к отысканию элемента в любом множестве, элементы которого упорядочены по отношению к какому – либо свойству.

Например: смотрим (рис. 2)

Можно знакомясь с человеком, угадывать его имя: сначала спросить про первую букву, расположена ли она в алфавите после буквы “П” , получив ответ, разделить соответствующую часть алфавита еще пополам и задать следующий вопрос о первой букве и так далее. Когда первая буква будет отгадана, начать отгадывать вторую. К концу этого процесса скорее всего, будете чувствовать себя старыми знакомыми, слегка поднадоевшими друг другу.

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

Устно решим задачу :

Сейчас открыто 110 химических элементов. На викторине по химии ведущий загадывал один из элементов, а участнику разрешалось задать последовательно 8 вопросов об этом элементе, на которые ведущий отвечал только “да” или “нет”, после чего участник должен назвать загаданный элемент. Зашедший на эту викторину программист – профессионал сказал, что если ему дадут таблицу Менделеева (так как он не помнит названий всех 110 элементов), то он обойдется 7 вопросами. Какие 7 вопросов вы могли бы предложить?

Алгоритм решения выглядит следующим образом. Воспользуемся таблицей Менделеева (рис.3) и зададим вопросы:

1. Этот элемент расположен по порядку возрастания порядкового номера правее 55 элемента? (110:2=55)
2. В зависимости от ответа, если “да”: элемент расположен правее 82 элемента?

Если “нет”: элемент расположен правее 28 элемента?

Вопрос: Как программист определил наименьшее количество задаваемых вопросов?

Ответ: 2 7 = 128, если 110 семь раз делить на 2, то получим всего два числа 1 и 2, то есть угадать будет легко.

Следующая задача :

Для выявления уровня способностей экспериментатор предлагает обучаемому тест, состоящий из 16 задач, расположенных в порядке возрастания сложности. Метод решения первой задачи экспериментатор объясняет сам, а затем предлагает обучаемому решить самую трудную, 16–ю задачу. Если обучаемый с ней справится, то экспериментатор предложит решить 15–ю; если не справится с 15–й, будет предложена 14–я и так далее, пока не обнаружится задача, которую обучаемый сможет решить. Её номер и показывает уровень способностей обучаемого. Вообще говоря, может случиться так, что обучаемому придется предложить решать все 15 задач. Заглянувший к экспериментатору профессиональный программист сказал, что уровень способностей можно выявить, предложив решить не более четырех задач. Объясните почему и как для этого надо организовать эксперимент.

Решение: Сначала необходимо уточнить, что промежуток от 2 до 16 (первая задача решена экспериментатором).

1. Предложить сначала решить 9 задачу;
2. если справился с 9–ой, то решать 13 – ю,
   иначе 5 – ю;
3. И так далее.

Можно изобразить рисунок, облегчающий понимание. (рис. 4)

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

Посмотрите на график функции.(рис. 5)

Возьмем какую – либо точку на отрезке [a ;b] расположенную левее корня (напомним, что корнем функции называется значение аргумента при котором функция обращается в ноль). В этой точке значение функции отрицательно и это сигнализирует нам, что искомый корень больше выбранного нами числа.

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

Получается очень похоже на игру “Угадай - ка”, только угадать надо число являющееся корнем уравнения.

Для этого прежде всего возьмем корень в “вилку”, то есть отрезок [a ;b] так, чтобы значение функции на его концах было разных знаков. Если непрерывная функция на отрезке меняет знак, то она имеет на этом отрезке хотя бы один корень. Затем найдем середину отрезка.

Вопрос: Как найти середину отрезка?

Ответ: (a +b)/2, то есть точка с=(a +b)/2

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

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

На практике почти все измерения производятся лишь с определённой точностью Е.

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

Составим блок-схему (метода деления пополам) (рис. 6)

А теперь решим задачу

Уравнение y=3cos(2x+4) имеет единственный корень на отрезке . Решим это уравнение с точностью до 0,001 методом половинного деления на ЭВМ

Переведем блок-схему на язык программирования.

DEFFN F(X)= 3*COS(2*X+4)
INPUT A,B,E
10 C=(A+B)/2
IF FN F(C)=0 THEN A=C: B=C: GOTO 20
IF FN F(A)* FN F(C)<0 THEN B=C ELSE A=C
20 IF B-A>E THEN 10
X=(A-B)/2
PRINT X
END

Label 1, 2;
Var a, b, e, c, x:real;
Function fx (y:real) :real;
Begin
Fx: =3*cos(2*y+4);
End;
Begin
Writeln(‘введи a, b, e’);
Readln(a, b, e);
1: c:=(a +b)/2; writeln(с);
if fx(c) =0 then Begin a:=c; b:=c; goto 2; end;
if fx(c)*fx(a) <0 then b:=c else a:=c;
2: if b-a>e then goto 1;
x: = (a+b)/2;
writeln(x);

end.

Ответ на экране ЭВМ

2
1.5
1.75
1.875
1.9375
1.90625
1.921875
1.9296875
1.92578125
1.927734375
1.9267578125
1.92724609375

Изменив функцию в данной программе, можно применять тот же метод для решения других уравнений, например x – cos(x) = 0; x – ln(x+2) = 0 на промежутке и тому подобное. Попробуйте поэкспериментировать с разными функциями и разными начальными значениями. “Охота” за корнями уравнения очень увлекательное занятие.

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

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

.

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

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

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

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

Из данного соотношения можно оценить число итераций k для достижения заданной точности :

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

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

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

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

1. Найти начальный интервал неопределенности одним из методов отделения корней. Задать погрешность расчета (малое положительное число ) и начальный шаг итерации () .

2. Найти середину текущего интервала неопределенности:

3. Необходимо найти значение функции в точках , и . Далее необходимо проверить два условия:

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

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

В результате находится новый интервал неопределенности, на котором находится искомых корень уравнения:

4. Проверяем новый отрезок на предмет заданной точности, в случае:

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

Если длина нового отрезка не достигает необходимой точности , то необходимо продолжить итерационный процесс и перейти к п.2 рассматриваемого алгоритма.