Пусть имеется уравнение вида f(x)= 0, где f(x) — заданная алгебраическая или трансцендентная функция.Решить уравнение — значит найти все его корни, то есть те значения x, которые обращают уравнение в тождество. Если уравнение достаточно сложно, то задача точного определения корней является в некоторых случаях нерешаемой. Поэтому ставится задача найти такое приближенное значение корня x_пр, которое отличается от точного значения корня x* на величину, по модулю не превышающую указанной точности (малой положительной величины) ε, то есть│x* – x_пр │< ε.Величину ε также называют допустимой ошибкой, которую можно задать по своему усмотрению.
Этапы приближенного решения нелинейных уравнений
Приближенное решение уравнения состоит из двух этапов:
- Отделение корней, то есть нахождение интервалов из области определения функции f(x), в каждом из которых содержится только один корень уравнения f(x)=0.
- Уточнение корней до заданной точности.
Метод бисекций
Если непрерывная на отрезке [a, b] функция y=f(x) принимает на концах его противоположные знаки, т.е. f(a)f(b)<0 (условие сходимости), то внутри этого отрезка содержится, по меньшей мере один корень уравнения f(x)=0. Корень заведомо будет единственным, если производная функции y=f'(x) существует и сохраняет постоянный знак внутри интервала (a, b), т.е. функция монотонна на отрезке [a, b].
Метод половинного деления (бисекции) это один из простейших методов решения нелинейных уравнений. Приводим алгоритм и геометрическую интерпретацию (рис. 1) этого метода.
Алгоритм метода бисекции:
Считаем, что отделение корней произведено и на интервале [a,b] расположен один корень, который необходимо уточнить с погрешностью ε.
Итак, имеем f(a)f(b)<0. Метод бисекции заключается в следующем. Определяем половину отрезка c=1/2(a+b) и вычисляем f(c). Проверяем следующие условия:
1. Если |f(c)| < ε, то c – корень. Здесь ε - заданная точность.
2. Если f(c)f(a)<0, то корень лежит в интервале [a, c].
3. Если f(c)f(b)<0, то корень лежит на отрезке [c, b].
Продолжая процесс половинного деления в выбранных подынтервалов, можно дойти до сколь угодно малого отрезка, содержащего корень ξ.
Так как за каждую итерацию интервал, где расположен корень уменьшается в два раза, то через n итераций интервал будет равен:
b_n-a_n=1/2n(b-a)
В качестве корня ξ. возьмем 1/2(a_n+b_n). Тогда погрешность определения корня будет равна (b_n – a_n)/2.
Если выполняется условие: (b_n – a_n)/2 < ε, то процесс поиска заканчивается и ξ = 1/2(a_n+b_n).
Метод хорд
Суть метода хорд состоит в разбиении отрезка [a,b] (при условии f(a)f(b)<0) на два отрезка с помощью хорды и выборе нового отрезка от точки пересечения хорды с осью абсцисс до неподвижной точки, на котором функция меняет знак и содержит решение, причём подвижная точка приближается к ε-окрестности решения.
Построение хорд продолжается до достижения необходимой точности решения ε.
Метод хорд применим для решения уравнения вида f(x)=0 на отрезке [a,b], если ни одна точка отрезка [a,b] не является ни стационарной, ни критической, то есть f’(x)≠0 и f"(x)≠0.
Условие начальной точки для метода хорд f(x)f"(x)<0.
Условие неподвижной точки для метода хорд f(x)f"(x)>0.
Сначала находим отрезок [a,b] такой, что функция f(x) дважды непрерывно дифференцируема и меняет знак на отрезке, то есть f(a)f(b)<0.
Далее применяем алгоритм решения.
Теорема. Пусть на отрезке [а; b] функция f (х) непрерывна вместе со своими производными второго порядка включительно, причем f(a)×f(b)<0, а производные f' (x) и f" (х) сохраняют свои знаки на [а; b], тогда существует такая окружность корня х* уравнения f(x)=0, что для любого начального приближения х0 этой окружности последовательность {хk}, вычисленная по формуле (1), сходится к корню х*.
Алгоритм метода хорд:
- Если f(a)·f’’(a)>0, то c=a, иначе если f(b)·f’’(b)>0, то c=b.
- Если f(a)·f’’(a)<0, то x=a, иначе если f(b)·f’’(b)<0, то x=b.
- Δx=f(x)·(x-c)/(f(x)-f(c)).
- x=x-Δx.
- Если |Δx|>ε, то идти к 3.