Материал: Методичка

Определение 2.1. Последовательность сходится с линейной скоростью или со скоростью геометрической прогрессии, если существует число , , такое, что .

Определение 2.2. Последовательность сходится со сверхлинейной скоростью, если существует последовательность , , такая, что .

Определение 2.3. Последовательность сходится с квадратичной скоростью, если существует число , такое что .

Определение 2.3 может быть распространено на любые случаи сходимости, для которых в неравенстве (*) показатель степени .

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

Действительно, так как , то в силу непрерывности получим , .

Итерационный процесс следует прекратить, когда будет достигнута заданная точность, то есть при выполнении условия

. (2.3)

Поскольку корень принадлежит отрезку , а – середина этого отрезка, то величина всегда будет меньше половины длины отрезка (рис. 2.5), то есть

.

Следовательно, условие (2.3) будет выполнено, если

. (2.4)

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

,

поэтому данный метод обладает линейной сходимостью.

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

, ,

где – целая часть числа (при и получим ).

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

. (2.5)

Соотношения (2.4) и (2.5) могут рассматриваться как условия прекращения итерационного процесса. Также необходимо иметь ввиду, что при уменьшении отрезка увеличиваются погрешности вычисления его длины за счет вычитания близких чисел.

Зададимся вопросом, почему среди всех возможных вариантов деления отрезка локализации корня выбран вариант половинного деления? Обоснованием целесообразности его использования может быть доказательство максимальной эффективности данного варианта в вычислительном плане. Пусть задан некоторый отрезок локализации корня, обозначим через точку деления данного отрезка, а через – длину того из отрезков и , на котором локализован корень. Исходя из постановки задачи, значение требуется минимизировать, при этом следует полагать, что . Минимальное значение может быть достигнуто в том случае, если , откуда . На рис. 2.6. приведен пример геометрической интерпретации обоснования наибольшей эффективности половинного деления отрезка локализации корня. Заметим, что аналогичное утверждение можно получить исходя из геометрического определняия вероятности. Если рассматривать отрезок как интервал неопределенности, положение корня уравнения на котором не известно, то выбирая способ его половинного деления, мы обеспечиваем равновероятность случаев положения корня на каждом из получаемых отрезков.

Рис. 2.6. Обоснование оптимальности половинного деления отрезка локализации корня.

2.2.2. Метод хорд

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

Рис. 2.7. Иллюстрация метода хорд.

Запишем уравнение прямой линии (хорды), проходящей через точки и :

.

Для отыскания точки пересечения хорды с осью абсцисс получим уравнение

.

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

, (2.6)

или при выполнении условия (2.5).

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

Замечание. Метод хорд иногда называют также методом пропорциональных частей: корень ближе к тому из концов отрезка его локализации, в котором модуль значения ординаты меньше. Данное утверждение основано на подобии треугольников и (рис. 2.7). В то же время данное утверждение не всегда верно, так как возможны случаи, аналогичные представленному на рис. 2.8.

Рис. 2.8. Нарушение пропорциональности частей отрезка локализации корня.

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

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

Рис. 2.9. Иллюстрации метода Ньютона.

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

, выражая , получим .

Аналогично могут быть найдены и следующие приближения. Формула для вычисления приближения имеет вид

_, . (2.7)

Из формулы (2.7) следует условие применимости метода: функция должна быть дифференцируемой и в окрестности корня не должна менять знак ( должна быть монотонной). В качестве условий окончания итерационного процесса может быть использовано условие (2.5) или (2.6).

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

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