Vladimir_S

(продолжение)

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

Начинаем с того, что выбираем стартовую точку x0. Этой точкой может быть один из концов интервала (a или b), а может быть просто точка вблизи предполагаемого корня (чем ближе, тем лучше).
(Лирическое отступление. Некоторые идиоты-"преподаватели" требуют от студентов, чтобы этой точкой непременно был один из концов интервала, причем не любой, а именно тот, где знаки функции и ее производной совпадают. Заявляю ответственно: подобные "украшательства" есть полная чушь, свидетельствующая лишь о некомпетентности этих самых...).
Далее, через точку (x0, F(x0)) проводим касательную к кривой y=F(x) до пересечения этой касательной оси абсцисс в точке х1. Таким образом, имеем прямоугольный треугольник с длинами катетов вертикального – F(x0), и горизонтального – расстояние между х0 и х1. Гипотенузой является отрезок касательной.
Если угол между касательной и осью абсцисс, отсчитанный от положительного направления последней, есть α, то из геометрии следует, что (x0-x1)=F(x0)/tg(α). Но тангенс угла наклона касательной есть ни что иное, как производная в точке х0, а потому, окончательно
x1 = x0 – F(x0)/F'(x0)
Далее берем функцию и производную в точке х1 и по той же формуле получаем х2, потом х3 и т.д. Точки х0, х1, х2, х3, ... и будут последовательными приближениями искомого корня.
К сожалению, метод не всегда устойчив. Например, если в стартовой точке производная близка к нулю, то точка х1 рискует оказаться далеко за пределами интервала и попасть в область, где функция либо не определена вовсе, либо успела пройти один или даже несколько экстремумов, и в таком случае процедура будет не приближать, а отдалять получаемые значения х1, х2 и т.д. от корня. Тем важнее становится этап предварительного исследования, о котором писалось выше.
Результат (обратите внимание, насколько быстро в методе Ньютона итерации сходятся к конечному значению):
4. Метод простой итерации

Тут хочу отметить сразу: метод, в общем случае, неустойчив, и выдаст ли программа желаемый результат или пойдет "вразнос" – это уж как повезет. Есть некие критерии сходимости, но они сложны и, в основном, избыточны, а потому рассматривать мы их не будем, а остановимся на самом алгоритме.
Первое, что нужно сделать, это преобразовать исходное уравнение F(x)=0 к виду х=Ф(х). Для уравнения, взятого в качестве примера, такое преобразование очевидно (функция Ф(х) там представлена). Дальше, нужно постараться найти число х0, близкое к искомому корню, и подставить его в ПРАВУЮ часть уравнения х=Ф(х). Тогда то, что получится слева, будет следующим приближением х1, каковое мы снова подставляем в правую часть и получаем х2, ну и т.д.
Результат:
5. Метод "десятичного деления"

Вообще-то официально такого не существует, более того, это метод выдумал я сам для своих целей. Вряд ли, конечно, это "открытие века", скорее всего он имеется в природе под каким-то другим названием, просто я не нашел. Мне он очень нравится, поэтому расскажу о нем здесь: вдруг кого-то заинтересует.
Возьмем в качестве стартовой точки нижнюю границу интервала a (верхняя b нам не понадобится) и еще зададим шаг h. Вот тут важно: этот шаг непременно должен быть степенью десяти (положительной, отрицательной либо нулевой), т.е. 10, 1000, 0.1, 1, 0.000001 и т.п. – в зависимости от задачи. Теперь, стартовав с x=a, начинаем увеличивать x с шагом h до тех пор, пока знак функции F(x) не изменится. Как только это произойдет, "отступим" на один шаг, уменьшим h ровно в 10 раз и повторим процедуру. Потом еще раз. И так будем повторять, пока не добьемся требуемой точности. В чем "изюминка" данного подхода? А в том, что каждое прохождение добавляет значащую цифру следующего разряда. То есть сколько нам надо их иметь, столько раз и следует прокручивать цикл. По-моему, очень даже удобно.
Метод абсолютно устойчив.

Результат: