Решение нелинейных уравнений

Рассматривается задача решения уравнения.

Решением этой задачи будут все значения аргумента х*, называемые корнями уравнения (3.1), обращающие его в тождество.

fix') = 0. Геометрически это означает, что корень уравнения соответствует точке пересечения графика функцииДх) с осью абсцисс. Корень называется простым, если/'(х*) Ф 0. В противном случае корень называется кратным. На рис 3.1 показан график некоторой функции fix). Точки и х₂ — простые (график пересекает ось абсцисс под ненулевым углом). Точки х₃ и х_л — кратные корни (в первой из них график лишь касается оси, а во второй имеет место точка перегиба), касательная к графику в этих точках идет параллельно оси абсцисс.

Рис. 3.1. Виды корней уравнения.

Точное решение задачи (3.1) может быть получено лишь в исключительных случаях. Более того, представить решение нелинейного уравнения в виде конечной формулы (в регулярной форме) обычно не представляется возможным. Так, для алгебраического уравнения вида.

формулы для определения корней найдены для степеней не выше четвертой. В остальных случаях требуется разработка методов поиска приближенных значений.

Если для уравнений все же построены конечные формулы для вычисления корней, потребность использования приближенных вычислений не исчезает. Причин этому две. Во-первых, параметры функции в формуле (3.1) обычно определяются из эксперимента и, следовательно, известны они лишь приближенно. Во-вторых, в процессе вычислений по найденным конечным формулам обычно возникают погрешности за счет округлений. Приведем интересный пример [4]. Пусть решается уравнение

Очевидно, что оно имеет точное решение х_г = 1,5, х₂ = 1,8. Предположим теперь, что в уравнении (3.2) значения коэффициентов были округлены, а истинный вид уравнения такой:

Это уравнение, казалось бы, очень близкое к уравнению (3.2), уже не имеет точного решения. Дело в том, что запись известной формулы решения квадратного уравнения приводит к выражению.

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

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

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

1. Локализация корней — нахождение отрезков числовой оси [а; Ь], которые содержат ровно один корень х 6 [а; Ь]. В какой точке отрезка находится корень — неизвестно, поэтому вместо отрезка локализации часто говорят об отрезке неопределенности. Предполагается, что во всех точках этого отрезка функция Дх) непрерывна. В противном случае рассматриваемая задача становится неопределенной.

Решение задачи локализации корней не формализовано, и в каждом конкретном случае она может решаться по-разному. Конечно, наиболее простым представляется построение графика функции Дх), из вида которого можно непосредственно определить отрезки локализации. Однако на практике такой подход не представляется реальным из-за сложности процесса построения графика функции. Часто нахождение корня в границах данного отрезка осуществляют исходя из физических соображений. Например, «согласно теории … где-то в окрестности точки х* значение функции Дх) должно равняться нулю». Эту окрестность и выбирают за отрезок локализации.

Иногда составляют таблицы значений левых частей уравнений вида (3.1), чтобы найти области знакопостоянства. Такой подход основан на известной из математического анализа теореме, которая гласит: если на отрезке [а; Ь] функция непрерывна и Да) -ДЬ) < 0, то внутри отрезка содержится хотя бы один корень уравнения (3.1).

В прикладной математике разработано большое количество методов уточнения значений корней. Схема построения большинства из них заключается в следующем: определяют некоторое начальное значение х₀, а затем последовательно уточняют его значениями х_ь х₂, х₃,… .За исходное значение корня выбирается, как правило, любая точка отрезка локализации, а все многообразие методов состоит в схеме вычисления следующего более точного значения корня. При этом предполагается, что процесс уточнения сходится.

Конечно, можно пойти и по пути угадывания. В качестве начального приближения выбрать любую точку числовой оси, где определена/(х). Применить один из методов (если выполнены условия его применимости) и найти «какой-то» корень уравнения (3.1). Затем назначить другое исходное приближение и повторить поиск. Такой процесс можно продолжить. Однако это уже не научный подход, а нечто другое.

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

Метод деления отрезка пополам. Этот метод, называемый также методом дихотомии или бисекции, был известен еще в древности. Его идея проста. Вначале определяется отрезок локализации. Затем его делят пополам. Находят ту его половину, где лежит искомый корень (теперь эта половина — отрезок локализации), и вновь делят отрезок пополам. Процесс заканчивают, когда длина отрезка неопределенности станет меньше требуемой точности е.

Пусть найден отрезок локализации [а; Ь], такой что Да) ДЬ) < < 0. Если за решение задачи выбрать середину этого отрезка х⁽⁰⁾, то ошибка не превысит половины его длины, т. е.

Если при этом , то задача решена. В противном случае требуется повысить точность решения, продолжая процесс.

Опишем процесс решения задачи более детально. Введем обозначения: а (°) = а, b = х = (Ь — а)/2. Если Да О)) • Дх) < 0, то искомый корень находится на отрезке [а®); х] (рис. 3.2). Это новый отрезок локализации, обозначим его [а⁽¹⁾; Ь⁽¹⁾]. В противном случае, когда Дх) • ДМ⁰⁾) < 0, искомый корень находится на отрезке [х; Ь®)], который является новым отрезком локализации, обозначим его также [а^); bW] (границы любого отрезка локализации обозначаем буквами а и b с верхними индексами, обозначающими число делений исходного отрезка локализации пополам).

Рис. 3.2. Решение уравнения методом деления отрезка пополам.

Половину длины отрезка локализации сравниваем с заданным уровнем точности. Если выполняется условие.

то середину найденного отрезка принимаем за искомое решение. Иначе описанный процесс продолжается.

Итак, после каждого г'-го шага деления отрезка локализации [а®_; Ь®] реализуем следующую последовательность действий.

1. Находим середину отрезка локализации:

• 2. Если Да®) • Дх) < 0, то а ('⁺¹> = а®, b (‘⁺¹) = х. В противном случае а (‘⁺¹) = х, = Ь®.
• 3. Если условие

не выполнено, то реализуем следующую итерацию: i := i + 1, переходя к п. 1. Иначе процесс закончен — искомое решение имеет вид

Пример 3.1 [5].

С точностью до 0,05 найти один из корней уравнения.

Решение. В точке х = 0 имеем ДО) = -1. Поскольку старшие степени имеют положительные коэффициенты, то при достаточно большом положительном аргументе функция имеет положительное значение. Поэтому если положить, например, х= 1, то/(1) = 1. Таким образом, [0; 1] — отрезок локализации, так как ДО) • Д1) = -1 < 0.

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

После шестой итерации получили величину /(0,8594) = -0,043 < < 0,05. Решение задачи закончено, и мы можем за искомый корень принять середину отрезка [0,8594; 0,875]. Ответ задачи: х = (0,8594 + + 0,875)/2 = 0,867.

Метод простой итерации. Рассмотрим один из наиболее важных для практики и теории метод простой итерации. Схема метода следующая. Вначале исходное уравнение (3.1) путем некоторых искусственных преобразований приводится к удобному для итерационного процесса виду

Поскольку это преобразование подобное, то, найдя решение уравнения (3.3), легко будет найти решение уравнения (3.1).

Затем произвольным образом или исходя из некоторых соображений выбирают исходное приближение искомого решения х⁽°), которое, будучи подставленным в правую часть равенства (3.3), даст новое значение решения х<4) = ф (х (°)). Найденное значение вновь подставляют в равенство (3.3) и получают х^ = ф (х<1)).

Подобный итерационный процесс продолжают по формуле.

до тех пор, пока не будет получено решение с заданной точностью.

Геометрическую интерпретацию этого метода легко уяснить, рассматривая рис. 3.3. Всегда ли сходится описанный итерационный процесс? Нет, и рис. 3.4 наглядно это иллюстрирует. Следовательно, процесс (3.4) далеко не всегда приводит к решению уравнения (3.1). Как быть? Ответ на этот вопрос дает следующая теорема: если в некоторой окрестности искомого решения функция ф непрерывно дифференцируема и удовлетворяет условию |ф'(х)|<�д, где 0 < q < 1, тогда независимо от выбора начального приближения итерационная последовательность сходится и справедлива следующая оценка достигнутой точности:

где х* — точное решение уравнение (3.1).

Действительно, если ф (х) — непрерывно дифференцируемая функция, то с учетом уравнения (3.3) согласно формуле Лагранжа имеем.

где точка с, лежит между х^(п) и х*. Если |ф'(<;)| < q < 1, то разности |х^(п)-х*| уменьшаются по крайней мере со скоростью геометрической прогрессии со знаменателем q, причем независимо от начальной точки х⁽⁰Г Используя свойства сходящейся геометрической прогрессии, получаем следующую оценку погрешности:

Поэтому процесс оканчивается, когда

Рис. 3.3. Сходимость метода простой итерации.

Рис. 3.4. Расходимость метода простой итерации.

Теперь очевидно, что чем меньше величина q, тем выше скорость сходимости метода. При | q > 1 процесс расходится. Это означает, что эффективность метода зависит от построения функции ф (х). Данный факт хорошо иллюстрирует следующий пример [4]. Пусть требуется решить простейшее уравнение.

Тогда если положить , то процесс расходится. Если же , то процесс сходится, и очень быстро.

Поскольку преобразование исходного уравнения к виду, удобному для проведения итерационного процесса, — процесс творческий, он может быть осуществлен по-разному. Одним из простейших является следующий прием. Вычисляется производная/' и находится мажорирующая ее величина М. Тогда можно положить.

где M>|/'(x)|Vxe[a;b].

Примечание 3.1. Наряду с условием достаточной близости «соседних» приближений значений искомого корня типа (3.6) может использоваться правило |/(х")| < 8.

Пример 3.2 [12].

Найти решение уравнения с точностью до 0,5 • 10^-4.

Решение. Вначале попытаемся определить отрезки неопределенности. Для этого вычислим значение функции в ряде точек и построим таблицу:

Отсюда следует, что корни уравнения, а их ровно три (решается алгебраическое уравнение третьей степени), находятся на отрезках [-3; -2], [-1; 0] и [0; 1]. Для иллюстрации метода простой итерации уточним значение корня, находящегося на первом отрезке.

Вначале преобразуем исходное уравнение к виду.

Для середины отрезка х₀ = -2,5 получаем.

Очевидно, что такая оценка справедлива для всех точек рассматриваемого отрезка, поэтому условия сходимости метода простой итерации на этом отрезке выполнены.

Разместим все вычисления в следующей таблице:

п	?*7?
	— 2,5.	— 2,84.
	— 2,84.	— 2,87 602.
	— 2,87 602.	— 2,87 910.
	— 2,87 910.	— 2,87 936.

Окончание таблицы

п	*п.
	— 2,87 936.	— 2,87 938.
	— 2,87 938.	— 2,87 938.

Всего лишь за пять итераций получен ответ: х ~ -2,87 938.

Для других найденных отрезков неопределенности требуется преобразование исходного уравнения к другому виду. Так, для отрезка.

[-1; 0] целесообразно следующее представление:

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

Метод Ньютона. В качестве развития метода простой итерации кратко рассмотрим славящийся своей высокой скоростью сходимости метод Ньютона, основная схема которого активно применяется в широком спектре решения различных нелинейных задач. Идея метода заключается в локальной линеаризации исходной задачи. Тем самым решение нелинейной задачи сводится к решению последовательности линейных задач. Действительно, пусть функция Дх) в окрестности некоторой точки x⁽") представлена в виде ряда Тейлора.

Отбрасывая в этом разложении все нелинейные члены, имеем.

Сравнивая формулы (3.1) и (3.7), приходим к уравнению

Решение этого линейного уравнения принимаем за новое приближенное значение искомой неизвестной, т. е.

Формула (3.8) носит название формулы Ньютона. По существу она описывает итерационный процесс получения приближенного решения. Для его начала должно быть выбрано начальное значение неизвестной х (°). Процесс гарантированно сходится лишь тогда, когда точка x.

Процесс останавливается, когда будет выполнено условие |x^(n₁) -xW | < е, где е, как и всегда, — верхняя граница требуемой точности.

Пример 3.3.

Решить методом Ньютона уравнение предыдущего примера/(х) = = х³ + Зх² — 1 = 0 с точностью е = 1(Н для корня, находящегося на отрезке [-1; 0].

Решение. В качестве начальной точки примем середину отрезка х₀= -0,5. Вычисления сведем в таблицу, показывая все промежуточные результаты:

Так быстро получить требуемое решение удается далеко не всегда. Метод Ньютона очень чувствителен к выбору начального приближения: чем ближе х₀ к искомому решению уравнения х*, тем больше шансов получить сходящийся процесс. На практике, когда уравнение достаточно сложное, часто поступают так. Начинают процесс (3.8), делая несколько шагов. Если оказывается, что величина |х^(,!_1) -х^(п)| с ростом п уменьшается, то решение продолжают, так как скорее всего процесс сходится. В тех случаях, когда не удается с ходу найти решение, рекомендуется изменить начальное значение неизвестной или применить некоторую модификацию метода Ньютона (см., например, работу [3]).

Примечание 3.2. Следует отметить, что погрешность вычисления корней ведет себя крайне нерегулярно и может рассматриваться как случайная величина. Более подробно об этом можно прочитать, например, в работе [1].