Численные методы уточнения корней (2 этапа):

1. Метод половинного деления – с простым способом выбора пробной точки путем деления промежутка существования корня пополам. Алгоритм такой: На каждом шаге итерации делят отрезок локализации пополам, за оценку корня берут середину отрезка: . Если значение f(xn) в точности =0, то корень считается найденным, итерации прерывают. Если же значение f(xn) не 0, то смотрят знак. (т.к. f(xn)<0 или f(xn)>0), и берут за новые, более узкие границы интервала локализации те, где f(x) принимает разные знаки. Затем весь блок повторяется. Критерий окончания итераций: , где - заданная погрешность.

2. Метод касательных (Ньютона). . (Начальное приближение решения x₀ берут таким, чтобы , иначе метод может не сойтись к решению (сходимость зависит от близости начального приближения x₀ к корню).) Критерий окончания итерационного процесса уточнения корня: . (Точность задается изначально).

3. Метод простых итераций. f(x) разлагают в форму: x=g(x). - В таком случан решение ищут итерационно: x_n+1=g(x_n). За начальное х₀ берут какое-нибудь значение из интервала локализации корня. Известно, что метод сходится со скоростью геометрической последовательности и справедлива оценка погрешности: . Если можно подобрать такую константу q, чтобы |g^/(x)|<=q<1, то метод гарантированно сходится (иногда может сойтись, даже если условие |g^/(x)|<1 не выполняется).

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

4. Метод хорд. расчетная формула для уточняемого корня на очередной итерации выглядит так: Метод хорд сходится медленнее, может вовсе не сойтись, во избежание чего начальное значение x₀ (и x₁) берут таким, чтобы . Сходимость зависит от близости начального приближения x0 к корню. Критерий окончания итераций тот же .

5. Метод ложного положения. . Критерий окончания

Метод дихотомии (бисекций).

И наче называется методом половинного деления. Пусть задан начальный интервал [x₀, x₁], на котором f(x₀)f(x₁) ≤ 0 (т.е. внутри имеется не менее чем один корень). Найдем x₂ = ½ (x₀ + x₁) и вычислим f(x₂). Если f(x₀)f(x₂) ≤ 0, используем для дальнейшего деления отрезок [x₀, x₂], если > 0 – используем для дальнейшего деления отрезок [x₁, x₂], и продолжаем деление пополам.

Итерации продолжаются, пока длина отрезка не станет меньше 2ξ ­– заданной точности. Тогда середина последнего отрезка даст значение корня с требуемой точностью. В качестве иного критерия можно взять | f(x)| ≤ ξ_y.

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

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

Метод хорд.

Идея метода проиллюстрирована рисунком. Задается интервал [x₀, x₁], на котором f(x₀)f(x₁) ≤ 0, между точками x₀ и x₁ строится хорда, стягивающая f(x). Очередное приближение берется в точке x₂, где хорда пересекает ось абсцисс. В качестве нового интервала для продолжения итерационного процесса выбирается тот, на концах которого функция имеет разные знаки. Условия выхода из итерационного цикла: или

| f(x)| ≤ ξ_y.

Для вывода итерационной формулы процесса найдем точку пересечения хорды (описываемой уравнением прямой) с осью абсцисс: ax₂ + b = 0, где ; b = f(x₀) ­­– ax₀.

Отсюда легко выразить .

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

Метод Ньютона (касательных).

Пусть x₀ – начальное приближение к корню, а f(x) имеет непрерывную производную. Следующее приближение к корню найдем в точке x₁, где касательная к функции f(x), проведенная из точки (x₀, f₀), пересекает ось абсцисс. Затем точно так же обрабатываем точку (x₁, f₁), организуя итерационный процесс. Выход из итерационного процесса по условию .

У равнение касательной, проведенной из точки (x₀, f₀): y(x) = f ^/(x₀)(x–x₀) + f(x₀) дает для y(x₁) = 0 следующее выражение:

, (1)

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

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

Недостатком метода можно указать необходимость знать явный вид первой и второй производных, так как их численный расчет приведет к уменьшению скорости сходимости метода. Иногда, ради упрощения расчетов, используют т.н. модифицированный метод Ньютона, в котором значение f ^/(x) вычисляется только в точке x₀, при этом число итераций увеличивается, но расчеты на каждой итерации упрощаются.

Метод секущих.

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

.

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

С ходимость может быть немонотонной даже вблизи корня. При этом вблизи корня может происходить потеря точности, т.н. «разболтка решения», особенно значительная в случае кратных корней. От разболтки страхуются приемом Гарвика: выбирают некоторое ξ_x и ведут итерации до выполнения условия . Затем продолжают расчет, пока убывает. Первое же возрастание может свидетельствовать о начале разболтки, а значит, расчет следует прекратить, а последнюю итерацию не использовать.

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

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

f(x) = 0 (2)

к эквивалентному уравнению x = φ (x). Этот переход можно осуществить разными способами, в зависимости от вида f(x). Например, можно положить

φ (x) = x + bf(x), (3)

где b = const, при этом корни исходного уравнения (2) не изменятся.

Если известно начальное приближение к корню x₀, то новое приближение x₁ = φ (x₀), т.е. общая схема итерационного процесса:

x_k+1 = φ (x_k). (4)

Наиболее простой критерий окончания процесса .

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

b = –1/f ^/(x), и итерационная формула (4) переходит в

,

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