Описание методов решения

Методом дихотомии (половинного деления) Пусть каким-либо методом найден отрезок изоляции корня [a, b] уравнения f (x)=0, где функция f (x) непрерывна на участке [a, b]. В дальнейшем требуется сузить этот отрезок так, чтобы его длина стала не больше заранее заданной точности вычисления корня ?, то есть чтобы |a-b|??.

Этот процесс сужения интервала, содержащего изолированный корень уравнения f (x)=0, называется уточнением корня.

В этом алгоритме отрезок изоляции корня [a, b] точкой c=(a+b)/2 делят пополам и вычисляют значение f (c). Если f (c)=0, то c — значение искомого корня уравнения, и задача решена. Если f©?0, то искомый корень уравнения содержится в одном из двух отрезков [a, c] или [b, c], на концах которого функция f принимает значения разных знаков. Из двух отрезков [a, c] и [b, c] выбираем тот, на котором функция меняет знак.

Если, то (точка смещается в точку).

Если, то (точка смещается в точку).

Полученный отрезок снова делим пополам и повторяем процесс до тех пор, пока не выполнится условие |a-b|??.

Тогда числа a и b являются приближенными значениями искомого корня с требуемой точностью ?, соответственно с недостатком и с избытком. За приближенное значение искомого корня берут число c=(a+b)/2, погрешность которого не превышает (b-a)/2n+1, где n — количество проведенных делений.

Метод хорд Пусть отрезок изоляции [a, b] корня х уравнения f (x) =0 найден, причем для определенности пусть f (a)0 и f'(x)>0. График функции y=f (x) проходит через точкиA (a;f (a)) и B (b;f (b)). Составим уравнение хорды АВ как прямой, проходящей через точки А и В:

Далее находим абсциссу x₁ точки пересечения хорды АВ с осью Ох, уравнение которой y=0:

Подставим первое уравнение системы во второе, x=xi, получим:

Число x₁ примем за первое приближение корня х. Далее, применяя этот же прием к отрезку изоляции [x1,b], на концах которого функция f (x) принимает противоположные знаки, получим второе приближение корня x₂:

Рисунок 5 — Графическое представление метода хорд Этот процесс можно продолжать неограниченно. В результате получим последовательность вложенных отрезков [a; b] [x₁; b] [x₂; b] … [x_n; b] … с неподвижным концом b. Последовательные приближения x_n (n = 1, 2, …) к точному значению корня х вычисляются по формуле.

называемой формулой метода хорд, и образуют монотонно возрастающую последовательность a = x₀< x₁< x₂< … < x_n< x_n+1< … < b, ограниченную сверху числом b.

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

Для оценки погрешности приближения x_n можно воспользоваться формулой.

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

В качестве начального приближения выбирается тот конец отрезка изоляции корня (или), в котором выполняется условие.

.

Выберем, например, , так как, и в точке В (x₀, f (х₀)) проведем касательную к кривой. Ее уравнение:

.

Найдем теперь точку пересечения x₁ касательной с осью Ох (в этой точке):

Эту точку x₁ принимаем за первое приближение искомого корня х.

Через точку С (x₁;f (x₁)) снова проведем касательную, абсциссу точки пересечения которой с осью Ох примем за второе приближение х₂ корня х.

Имеем:

;

.

Продолжая этот процесс далее, получим рекуррентную формулу,.

называемую формулой метода касательных.

Полученная числовая последовательность x₀>x₁>x₂>…>x_n>x_n+1>…>a сходится к корню уравнения х.

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

.

Рисунок 6 — Графическое представление метода касательных Метод простых итераций (последовательных приближений) Пусть известно, что нелинейное уравнение имеет на отрезке [a, b] единственный вещественный корень. Требуется найти этот корень с заданной точностью. Применяя тождественные преобразования, приведем исходное уравнение к виду x=?(x).

Выберем произвольно приближенное значение корня и вычислим x₁=?(x₀). Найденное значение x₁ подставим в правую часть соотношения x=?(x) и вычислим x₂=?(x₁). Продолжая процесс вычислений дальше, получим числовую последовательность .

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

Достаточное условие, при котором итерационный процесс сходится, определяет следующая теорема: пусть функция ?(х) определена и дифференцируема на отрезке [a, b], причем все ее значения и выполняется условие, тогда процесс итераций сходится независимо от начального значения и предельное значение — единственный корень уравнения на [a, b] .

Метод простых итераций и почти все другие итерационные методы имеют два достоинства:

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

Недостатки метода:

• — трудность приведения уравнения к виду .
• — если начальное приближение далеко от корня, то число итераций достаточно большое. Объем вычислений возрастает.

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

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

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

В данном задании необходимо задать точность вычислений, границы отрезка [a;b], начальное приближение х.

Выходными данными являються корни.