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

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

Рис. 1

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

Алгоритм данного метода можно записать так:

1.Ввести данные (a, b, е).

2.Если нужная точность достигнута (| b - a | < 2е) то иди к п.6

3.Возьми середину очередного отрезка (x= ( a + b )/ 2).

4.Если значения функции в точках a и c одного знака (f(a)*f(c)>0), то в качестве следующего отрезка взять правую половину (а=c), иначе левую (b=c).

5.Иди к п.2.

6.Напечатать ответ c=...

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

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

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

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

Реализация удаления корней: « Если x1 есть простой корень уравнения f(x) непрерывна, то вспомогательная функция g(x)=f(x)/(x-x1) непрерывна, причем все нули функций f(x) и g(x) совпадают, за исключением x1, то он будет нулем g(x) кратности на единицу меньше; остальные нули обеих функций по-прежнему будут одинаковы». Калиткин Н.Н. «Численные методы» стр.140

Пример. Необходимо методом дихотомии уточнить корень уравнения х 3 - 3 х +1 = 0 с точностью 10 -3 (табл. 2) .

Таблица 2

a10 - b10 = 0,3468 - 0,3477 = 0,0009 < , где = 0,001.

0,347 .

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

Или метод последовательных приближений. Чтобы применить этот метод для решения уравнения (1) необходимо преобразовать его к виду . Далее выбирается начальное приближение и вычисляется x1, затем x2 и т.д.:

x1 = (x0);

x2 = (x1);

…;

xk = (xk-1);

Если xn стремится к некоторому пределу x, то этот предел и есть корень уравнения.

Полученная последовательность сходится к корню при выполнении следующих условий:f

1) функция (x) дифференцируема на интервале [a, b].

2) во всех точках этого интервала (x) удовлетворяет неравенству:

0 q 1 (2)

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

. (3)

Критерий вида

, (4)

может использоваться только при 0 q Ѕ. Иначе итерации заканчиваются преждевременно, не обеспечивая заданную точность. Если вычисление q затруднительно, то можно использовать критерий окончания вида

; . (5)

Возможны различные способы преобразования уравнения (1) к виду . Следует выбирать такой, который удовлетворяет условию (4), что порождает сходящийся итерационный процесс, как, например, это показано на рис. 2, 3. В противном случае, в частности, при (x)>1, итерационный процесс расходится и не позволяет получить решение (рис. 4).

Материал с сайта allbest.ru

Рис. 2

Материал с сайта allbest.ru

Рис. 3

 Материал с сайта allbest.ru

Рис.4

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

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

Даже грубые ошибки не могут причинить видимого вреда. Но только если ошибка не выбрасывает приближение за пределы области сходимости.

Пример. Необходимо методом итераций уточнить корень [0;1] уравнения: х 3 - 3х +1 = 0, с точностью 10 -3 (табл. 3).

Преобразованное уравнение:

 .

Таблица 3

х 4 - х 3 <

0,347.

5. Метод хорд

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

Идея метода хорд состоит в том, что на достаточно малом промежутке [a, b] дугу кривой y = f(x) можно заменить хордой и в качестве приближенного значения корня принять точку пересечения с осью абсцисс. Рассмотрим случай, когда первая и вторая производные имеют одинаковые знаки, т.е. f '(x)f (x) . Тогда уравнение хорды, проходящей через точки A0 и B, имеет вид

. (6)

Приближение корня x = x1, для которого y = 0, определяется как

. (7)

Аналогично для хорды, проходящей через точки A1 и B, вычисляется следующее приближение корня

. (8)

В общем случае формула метода хорд имеет вид:

. (9)

Если первая и вторая производные имеют разные знаки, т.е.

f '(x)f "(x) ,

то все приближения к корню x* выполняются со стороны правой границы отрезка [a, b], как это показано на рис. 6, и вычисляются по формуле:

. (10)

Выбор формулы в каждом конкретном случае зависит от вида функции f(x) и осуществляется по правилу: неподвижной является граница отрезка [a, b] изоляции корня, для которой знак функции совпадает со знаком второй производной. Формула (9) используется в том случае, когда f(b)f "(b) . Если справедливо неравенство f(a)f "(a) , то целесообразно применять формулу (10).

Рис. 5 Рис. 6

Рис. 7 Рис. 8

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

. (11)

Тогда условие завершения вычислений записывается в виде:

. (12)

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

Пример. Необходимо методом хорд уточнить корень [0;1] уравнения х 3 - 3х + 1 = 0 с точностью 10 -3 (табл. 4) .

;

а = 0; f(a) = 1.

Таблица 4

x 5 - x 4 < .

0,347.

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

Пусть уравнение (1) имеет корень на отрезке [a, b], причем f '(x) и f "(x) непрерывны и сохраняют постоянные знаки на всем интервале [a, b].

Геометрический смысл метода Ньютона состоит в том, что дуга кривой y = f(x) заменяется касательной. Для этого выбирается некоторое начальное приближение корня x0 на интервале [a, b] и проводится касательная в точке C0(x0, f(x0)) к кривой y = f(x) до пересечения с осью абсцисс. Уравнение касательной в точке C0 имеет вид

y = f(x0) + f '(x0)(x - x0). (13)

Далее за приближение корня принимается абсцисса x1, для которой y = 0:

(14)

Затем проводится касательная через новую точку C1(x1, f(x1)) и определяется точка x2 ее пересечения с осью 0x и т.д. В общем случае формула метода касательных имеет вид:

(15)

В результате вычислений получается последовательность приближенных значений x1, x2, ..., xi, ..., каждый последующий член которой ближе к корню x*, чем предыдущий.

Начальное приближение x0 должно удовлетворять условию:

f(x0) f (x0) 0. (16)

В противном случае сходимость метода Ньютона не гарантируется, так как касательная будет пересекать ось абсцисс в точке, не принадлежащей отрезку [a, b]. На практике в качестве начального приближения корня x0, обычно выбирается одна из границ интервала [a, b], т.е. x0 = a или x0 = b, для которой знак функции совпадает со знаком второй производной.

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

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

, (17)

т.е. значение производной достаточно вычислить только один раз в начальной точке. Геометрически это означает, что касательные в точках Ci(xi, f(xi)), где i = 1, 2, ..., заменяется прямыми, параллельными касательной, проведенной к кривой y = f(x) в начальной точке C0(x0, f(x0)).

В заключение необходимо отметить, что все изложенное справедливо в том случае, когда начальное приближение x0 выбрано достаточно близким к истинному корню x* уравнения. Однако это не всегда просто осуществимо. Поэтому метод Ньютона часто используется на завершающей стадии решения уравнений после работы какого-либо надежно сходящегося алгоритма, например, метода половинного деления. Скорость сходимости велика для простого корня и соответствует скорости геометрической прогрессии для кратного корня.

Упрощенный вариант метода

Если const , то (см. рис. 9)

Рис. 9

. (18)

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

Пример. Необходимо методом касательных уточнить корень [0;1] уравнения

с точностью 10 -3 (табл. 5) .

.

Таблица 5

x 3 - x 2 < .

0,347 .

8. Метод хорд и касательных

Применяется только в том случае, когда f'(X) и f''(X) не изменяют знака на отрезке [a,b], т.е. функция f(X) на отрезке [a,b] монотонна и не имеет точек перегиба.

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

(| b - a | < 2е). (19)

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

Также несложно заметить, что касательная проводится либо все время из правого, либо все время из левого конца. Будем считать для определенности, что этот конец - b .

Формулы, употребляемые в методе, хорошо известны из аналитической геометрии:

Уравнение хорды, проходящей через точки (a,f(a)) и (b,f(b)):

трансцендентное уравнение дихотомия

y = f(a)+(x-a)*(f(b)-f(a))/(b-a),

откуда точка пересечения с осью Оx:

x= a - f(a) *(b-a)/(f(b)-f(a)).

Уравнение касательной, проходящей через точку (b,f(b)): y=f(b)+f'(b)(x-b), откуда точка пересечения с осью Оx:

x= b - f(b)/f'(b).

При составлении алгоритма снова естественно использовать для концов отрезка только две переменные a и b и писать:

a= a - f (a) *(b-a)/ (f (b)-f (a)) (20)

b= b - f(b)/f'(b) (21)

Однако, в этом случае важен порядок формул (20) и (21).

Пример. Необходимо комбинированным методом уточнить корень 0;1 уравнения: х 3 - 3 х +1 = 0, с точностью 10 -3 (табл. 6) .

,

.

Таблица 6

< . 0,347 .

8. Заключение

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

9. Литература

1. Вычислительная техника и программирование: Учеб. для техн. вузов/ А.В. Петров, В.Е. Алексеев, А.С. Ваулин и др. - М.: Высш. шк., 1990г. 479 стр. ISBN: 1522608, 1522607.

2. Гусев В.А., Мордкович А.Г. - Математика: Справ. материалы: Кн. для учащихся. - 2-е изд. - М.: Просвещение, 1990г. - 416 стр. ISBN 5-09-001292-X.

3. Березин В.Л., Харитонова К.Ю. «Просмотрщик решений трансцендентных уравнений и его применение в задачах волоконной оптики», Сб. науч. тр. Механика. Математика, Саратов: Изд-во Сарат. ун-та, 2004г. 168-170 стр.

4. Мак-Кракен Д., Дорн У. Численные методы и программирование на ФОРТРАНе. - М.: Мир, 1977г. - 584 стр.

5. Демидович Б.П., Марон И.А. «Основы вычислительной математики». - М.: Наука, 1970г. - 664 стр.

6. http://www.simumath.net/library/book.html?code=Alg_Equations_introduction

7. http://habrahabr.ru/post/132366/

8. Пантилеев, Киреев «Численные методы в примерах и задачах». Издательство: Высшая школа. Год: 2008. 480 стр.. ISBN: 978-5-06-004763-9,5-06-004763-6.

9. Д.П.Костомаров, А.П.Фаворский «Вводные лекции по численным методам». Санкт-Петербургский государственный электротехнический университет "ЛЭТИ". Серия: Классический университетский учебник. Издательство: М.: Логос. Переплет: твердый; 184 стр.; 2004 г. ISBN: 5-94010-286-7.

10. Приложение

Листинг программы для решения трансцендентного уравнения

Находит лишь один корень, т.к. удаление других корней не реализовано.

uses crt;

var

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

function f(y: real):real; //функция

begin

f := y*y*y-y+1; //заданное уравнение

end;

begin

ClrScr;

Writeln('Введите требуемую точность'); //ввод точности вычисления

readln(eps);

Writeln('Введите a'); //задание интервала

readln(a);

Writeln('Введите b'); //задание интервала

readln(b);

c := (a+b)/2;

while abs(b-a) > eps do

begin

if f(a)*f(c) < 0 then b := c //проверка значения

else a := c;

c := (a+b)/2; //разбитие отрезка

end;

x := (a+b)/2;

Writeln('x = ', x:6:10);

Readln;

end.

Блок схема программы:

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