Название: Информатика.Алгоритмы и программы вычислительных задач микроэлектроники - Метод.(Н.В. Усольцев)

Жанр: Информатика

Просмотров: 941

2. основные методы решения нелинейных уравнений

2.1. Методы, требующие задания нулевого приближения

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

Итерации выполняются до тех пор, пока не будет выполняться условия:

                                                                           (2a)

                                                                                (2b)

где       - заданная абсолютная погрешность определения корня;

- заданная погрешность невязки левой части уравнения с нулем.

Из методов этого типа наиболее распространены методы простых итераций и Ньютона.

Метод простых итераций применим для уравнений, которые можно привести к виду

                                               ,                                                                           (3)

из которого вытекает итерационная формула:

                                                                      (4)

Итерации выполняются по ней до тех пор, пока не будет выполняться условие (2a). Условие (2b) в этом методе не может быть использовано.

Итерационный процесс сходится к значению корня, если на интервале итераций выполняется условие:                           

                                                                   (5)

Блок-схема алгоритма метода простых итераций представлена на рис. 5.1

Метод Ньютона является наиболее быстро сходящимся и поэтому одним из наиболее используемых.

Суть метода основана на том, что левая часть уравнения  в окрестности  линеаризируется по вычисленным значениям самой левой части  и ее первой производной

                                                 (6)

и находится корень полученного линейного уравнения

,

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

Это приводит к итерационной формуле:

                                                  (7)

Итерации выполняются из заданного нулевого приближения  до тех пор, пока не будут выполняться условия (2). Блок-схема алгоритма метода Ньютона приведена на рис. 5.2.

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

Рис. 5.1. Блок-схема алгоритма метода простых итераций

Простым и эфффективным способом добиться сходимости во многих случаях  является ограничение ньютоновского приращения. Если величина приращения на k-той итерации

получается больше  некоторого задаваемого предельного значения , то оно искусственно ограничивается этой величиной:

(8)

При ограничении знак приращения  должен быть выбран равным знаку приращения  .

Рис. 5.2. Блок-схема алгоритма метода Ньютона

2.2. Методы, требующие задания интервала поиска корня

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

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

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

Блок схема алгоритма метода половинного деления представлена на рис. 5.3.

Метод хорд  в чем-то похож на метод половинного деления. Суть метода заключается в следующем. На каждой итерации по двум точкам - границам интервала –  и  левая часть уравнения линеаризируется и находится корень полученного линейного уравнения

                                            (9)

Затем та граница интервала ( или ), где знак левой части уравнения F совпадает со знаком ее в точке x, переносится в эту точку и все повторяется до тех пор, пока не будут выполняться условия (2). Блок-схема алгоритма метода хорд представлена на рис. 5.4.

Рис. 5.3. Блок-схема метода половинного деления (бисекции)

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