Размещено на http://www.allbest.ru/

1. Отделение корней алгебраических и трансцендентных уравнений

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

F(x) = 0, (1)

где F(x) -- алгебраическая или трансцендентная функция.

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

Решение указанной задачи в достаточно общем случае начинается с отделения корней, т. е. с установления:

· количества корней;

· наиболее «тесных» промежутков, каждый из которых содержит только один корень.

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

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

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

f₁(x)=f₂(x) (2)

В этом случае строятся графики функций f₁(x) и f₂(x), а потом на оси х отмечаются отрезки, локализующие абсциссы точек пересечения этих графиков.

Для графического отделения корней уравнения преобразуем его к равносильному уравнению и отдельно построим графики функций (рис 1.)

Рис.1 Иллюстрация к отделению корней уравнения.

Из графика вполне очевидно, что уравнение имеет единственный корень E, и этот корень находится на отрезке [0; 1].

При решении задачи об отделении корней бывают полезными следующие очевидные положения:

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

Если функция F(x) к тому же еще и монотонна, то корень на отрезке [а; b] единственный.

Вычислим для проверки значения функции F(x) = 2x - cosx на концах отрезка [0; 1]: F(0) = -1; F(l) = 2,54. Как видно, корень на отрезке [0; 1] действительно имеется.

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

Пусть имеется уравнение F(x) = 0, причем известно, что все интересующие вычислителя корни находятся на отрезке [А; В], на котором функция F(x) определена, непрерывна и F(A)*F(B) < 0. Требуется отделить корни уравнения, т.е. указать все отрезки [а; b] принадлежащие [А; В], содержащие по одному корню.

Будем вычислять значения F(x), начиная с точки х-А, двигаясь вправо с некоторым шагом h (рис. 2).

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

Рис. 2. Иллюстрация к процессу отделения корня

Отделить корни уравнений на отрезке .

Ниже приведена программа отделения корней уравнения на языке Turbo Pascal. Результатом решения поставленной задачи будут выводимые на экран (или на печать) в цикле значения параметров х₁ и х₂ (концов выделенных отрезков).

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

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

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

Обратим внимание на то, что надежность рассмотренного алгоритма отделения корней уравнения зависит как от характера функции F(x), так и от выбранной величины шага h. Действительно, если при достаточно малом значении h на концах текущего отрезка [х; х + h] функция F(x) принимает значения одного знака, естественно ожидать, что уравнение F(x) = 0 корней на этом отрезке не имеет. Это, однако, не всегда так: при несоблюдении условия монотонности функции F(x) на отрезке [х; х + h] могут оказаться корни уравнения (рис. 3, а). Не один, а несколько корней могут оказаться на отрезке [х; х + h] и при соблюдении условия F(A)*F(B) < 0 (рис. 3, б). Предвидя подобные случаи, следует выбирать при отделении корней достаточно малые значения h.

Рис. 3. Зависимость количества корней функции F(x) на отрезке [х, х+ h] от характера функции и величины шага h: а -- функция не меняет знака на отрезке [х, х + h], но не монотонна, поэтому на отрезке [х, х+ h] имеются корни; б -- функция на отрезке [х, х + h] меняет знак, но немонотонна, поэтому корней на отрезке не один, а несколько.



2. Уточнение корней уравнения методом половинного деления

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

Описанный выше способ табулирования может рассматриваться и как способ уточнения корня (хотя и крайне неэффективный). При этом можно либо постепенно уменьшать шаг табулирования, приближая его к значению ?, либо сделать это сразу, полагая h = ?. В любом случае получим b - а < ?. Тогда в качестве искомого значения корня можно выбрать середину этого отрезка, т.е. положить = (а + b)/2.

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

Пусть уравнение F(x)=0 имеет на отрезке [а; b] единственный корень, причем функция F(x) на этом отрезке непрерывна. Разделим отрезок [а; b] пополам точкой с = (а + b)/2. Если F(c) <> 0 (что практически наиболее вероятно), то возможны два случая: F(x) Меняет знак либо на отрезке [а; с] (рис. 4, а), либо на отрезке [a; b] (рис. 2.6, б). Выбирая в каждом случае тот из отрезков, на котором функция меняет знак, и продолжая процесс половинного деления дальше, можно дойти до сколь угодно малого отрезка, содержащего корень уравнения.

Рис. 4. К решению уравнения F(x) методом половинного деления: а -- функция F(x) меняет знак на отрезке [а; с]; б -- функция F(x) меняет знак на отрезке [c; b]

Метод половинного деления вполне можно использовать как метод решения уравнения с заданной точностью. Действительно, если на каком-то этапе процесса получен отрезок [а; b], содержащий корень, то, приняв приближенно х = (а + b)/2, получим ошибку, не превышающую значения

(3.)

(заметим, что речь в данном случае идет о погрешности метода). Метод половинного деления требует утомительных ручных вычислений, однако он легко реализуется с помощью программы на компьютере (блок-схему алгоритма см. на рис. 5). Отметим, что даже если на каком-то этапе деления отрезка пополам получится F(c) = 0, это не приведет к сбою алгоритма.

Рис. 5. Блок-схема алгоритма уточнения корня уравнения F(x)=0 на отрезке [а; b] с точностью е методом половинного деления

Уравнение имеет единственный корень на отрезке [0,4; 0,5] (см. пример 1). Решим это уравнение с точностью до 1*10^-4 методом половинного деления с помощью программы для компьютера.

В соответствии с блок-схемой алгоритма, изображенной на рис. 5, программа на языке Turbo Pascal имеет вид, также сразу покажем результат работы программы:

В приведенной программе заданная точность обозначена eps, a граница погрешности текущего значения корня определяется через разность b - а. Еще раз напомним, что эта разность отождествлена в алгоритме с погрешностью метода; вычислительная же погрешность значения х как результат ошибки вычисления по формуле х= (а + b)/2 в программе в явном виде не регистрируется. И связана только с погрешностью машинного представления. программа алгебраический уравнение трансцендентный

3. Итерационные методы уточнения корней

Метод простой итерации

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

(4)

Сделать это можно множеством способов. Простейший и очевидный - добавить х к левой и правой частям уравнения (4).

Пусть - корень уравнения (4), а - полученное каким - лио способом на этапе отделения корней грубое приближение к корню . Подставляя в правую часть уравнения (4), получим некоторое число . Проделаем то же самое с , получим и т.д. последовательно применяя рекуррентное соотношение образуем итерационную последовательность:

(5)

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

Предположим, что существует отрезок , содержащий все члены последовательности (5). Если на отрезке функция возрастает, то итерационная последовательность является монотонной. Если убывает, то она является колеблющейся.

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

(6)

Условие (6) имеет в математической литературе собственное название: условие Липщица.

Рис. 6.а - сходящаяся последовательность, б - расходящаяся

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

(7)

Называемая формулой Лагранжа (или формулой конечных приращений)

Сравнивая (6) и (7) приходим к выводу: если существует такое число , что для любых



(8)

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

Итак, общая схема решения уравнения (1) методом итерации такова:

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

2. Преобразовать уравнение (1) к равносильному уравнению вида (4).

3. Найти и проверить, является ли функция сжимающей на отрезке .

4. Если сжимаемость имеет место:

a) Задаться точностью е нахождения приближенного значения корня;

b) Задаться первым членом итерационной последовательности - начальным приближением к корню;

c) Построить следующий член итерационной последовательности (6);

d) Всякий раз, получив очередной член итерационной последовательности, проверять, выполняется ли условие: или

(9)

e) Если условие (9) выполняется, то принять за результат, иначе вновь выполнить пунк с).

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

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

Рассмотрим простейший из них. Преобразуем уравнение (1) к равносильному уравнению

(10)

где - константа, отличная от нуля.

Таким образом, . Условие (8) приобретает вид , или, иначе

(11)

Если удастся подобрать значение так, чтобы условие (11) выполнялось, то метод итераций применим.

Рассмотрим в начале случай, когда . Второе из неравенств (11) сводится к условию > 0, а первое - к условию . Полагая

, (12)

Получим из (10) итерационную формулу

(13)

Критерий выхода из итерационного процесса:

Поскольку считается, что , то , где .

Если , то, рассуждая аналогично, получим и итерационную формулу

(14)

Уточнить корень уравнения методом простой итерации на отрезке [0,4;0,5] с заданной точностью.

Исходное уравнение можно привести к виду , в этом случае . Подберем константу из условия (12). Поскольку производная на отрезке положительна и монотонно возрастает, то достигает максимума в точке 0,5. . Следовательно, положим . Таким образом, имеем рекуррентное соотношение

Найдем критерий выхода из итерационного процесса:

,

где .

Малое значение q обеспечивает быструю сходимость итерационного процесса.

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

4. Методы Ньютона

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

Оба метода основаны на следующем приеме. Пусть уравнение (1) имеет единственный корень на отрезке . Преобразуем его к равносильному уравнению

(15)

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

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

(16)

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

1) является дважды дифференцируемой на отрезке ;

2) обе производные - первая и вторая - не меняют знак на этом отрезке, т.е. функция монотонна и не меняет характера выпуклости; ситуация иллюстрируется одним из вариантов на рис. 7.

В такой ситуации за берется тот конец отрезка , на котором функция и ее вторая производная имеют одинаковые знаки, т.е. выполняется условие . Очевидно, что это левый конец на рис.8, а и г и правый конец на рис. 7, б и в.

Допустим в дополнение к сделанным ранее предположениям, что также непрерывна на . Докажем, что отображение , соответствующее формуле (16), является сжимающим в некоторой окрестности корня уравнения . Для этого, как показано выше, достаточно, чтобы в указанной окрестности имело место неравенство . Вычислим производную

.

Рис. 7. Четыре возможности поведения функции в окрестности корня: а - функция убывает и выпукла; б - функция убывает и вогнута; в - функция возрастает и вогнута; г - функция возрастает и выпукла

Непосредственно в корне имеем

,

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

Для оценки расстояния от очередного приближения до корня можно использовать как общее соотношение (9), так и следующий прием по формуле Лагранжа

Отсюда получаем

(17)

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

Можно показать, что если имеет на непрерывную вторую производную , то погрешности на n - м и (n+1) - м шагах связаны неравенством

. (18)

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

Рассмотренный метод называется методом касательных потому, что если обратиться к графической иллюстрации (рис.8), то точка , определяемая по формуле (16) при n=0, есть точка пересечения касательной, проведенной к графику функции в точке с абсциссой , с осью абсцисс.

Рис. 8. геометрический смысл метода касательных

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

Уточнить корень уравнения методом касательных на отрезке [0,4;0,5] с заданной точностью.

Результат работы программы:

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

Если положить в (15) , а в качестве с взять тот конец промежутка , на котором , то приходим к итерационному методу:

(19)

называемому методом хорд (или методом секущих).

В качестве в этом случае следует принять тот конец промежутка , который остался после выбора c (т.е. если , то или наоборот). Далее последовательность строится по формуле (19). оценка степени приближения к корню возможна с помощью неравенства (17). (Оно было получено с помощью формулы Лагранжа, не зависящей от рассматриваемых методов)

Геометрический смысл метода (благодаря которому он получил название) проиллюстрирован на рис.9. В данном случае , , соответствует точке пересечения хорды, соединяющей концы кривой, с осью абсцисс. Далее находится точка на кривой с абсциссой , проводится следующая хорда и т.д.

Рис.9. геометрический смысл метода хорд.

Уточнить корень уравнения методом хорд на отрезке [0,4;0,5] с заданной точностью.

Размещено на Allbest.ru

...