Использование обратной интерполяции.

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

Примеры итерационных методов решения нелинейных уравнений

Введение.

Пусть задана функция действительного переменного. Требуется найти корни уравнения

(4.1)

или, что то же самое, нули функции .

Уже на примере алгебраического многочлена известно, что нули могут быть как действительными, так и комплексными. Поэтому более точная постановка задачи состоит в нахождении корней уравнения (4.1), расположенных в заданной области комплексной плоскости. Можно также рассматривать задачу нахождения действительных корней, расположенных на заданном отрезке.

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

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

Прежде чем переходить к изложению конкретных итерационных методов, отметим два простых приема определения действительных корней уравнения (4.1). Предположим, что определена и непрерывна на .

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

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

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

(4.2)

и для нее повторяется процесс нахождения корня.

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

Он состоит в том, что уравнение (4.1) заменяется эквивалентным уравнением

(4.3)

и итерации образуются по правилу

, (4.4)

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

, (4.5)

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

Отметим, что в форме метода простой итерации (4.4) можно записать, по существу, любой одношаговый итерационный метод.

В частности, если , то получим метод релаксации

, , (4.6)

для которого , и метод сходится при условии

. (4.7)

Метод Ньютона.

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

и за следующее приближение возьмем корень уравнения , т.е.

. (4.8)

Вообще, если итерация известна, то следующее приближение в методе Ньютона определяется по правилу

, (4.9)

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

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

Модифицированный метод Ньютона

, (4.10)

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

Метод (4.10) гарантирует отсутствие деления на нуль, если .

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

Этот метод получается из метода Ньютона (4.9) заменой разделенной разностью , вычисленной по известным значениям и . В результате получаем итерационный метод

, , (4.11)

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

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

Интерполяционные методы.

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

Получим формулы метода парабол. Пусть приближения , , известны. Построим многочлен Ньютона (см. лекции 1.2, 1.3).

,

где (см. лекция 1.2, формулы (2.6), (2.7))

, .

Обозначим , тогда уравнение примет вид

, (4.12)

где

, , .

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

Использование обратной интерполяции.

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

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

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