2.3. Уточнение корней

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

Идея метода основывается на том, что корень уравнения – это такое число, при подстановке которого в уравнение, оно обращается в тождество. Если переписать исходное уравнение в несколько ином виде, а именно: x=g(x), то при подстановке точного значения корня равенство все равно сохранится.

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

Пусть x₀ будет исходным приближенным значением корня уравнения x=g(x). Тогда в качестве следующего приближения примем: x₁=g(x₀), второе приближение получим, подставив в правую часть уравнения первое приближение: x₂=g(x₁) и т.д. В общем виде: x_n=g(x_n-1).

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

Для определения достижения точности пользуются неравенством или .

Блок-схема метода:

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

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

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

Генерирующее отношение вида x=g(x), можно получить и иным способом. Рассмотрим геометрическую интерпретацию метода.

Выберем начальное приближение x₀, близкое к корню уравнения f(x)=0. Проведем касательную к кривой y=f(x) в точке (x₀, f(x₀)). Она пересечет ось Ох в некоторой точке х₁.

Так как тангенс угла наклона касательной к графику функции в точке (x₀, f(x₀)) равен производной функции в этой точке, можно найти расстояние между точками х₀ и х₁, обозначим это расстояние

Тогда координату точки х₁ можно определить следующим образом:

Аналогично можно найти точки х₂, х₃, …, х_n, …

Таким образом, для расчета приближений в методе Ньютона используется формула:

Счет прекращается при достижении достаточного малого значения.

Это самый быстрый метод. Скорость сходимости в большей мере зависит от удачного выбора исходной точки.

Если в процессе вычислений на каком-то шаге тангенс угла наклонной касательной обращается в нуль, т.е. f`(x)=0, то применение метода усложняется.

Сходимость метода обеспечивается при следующих условиях:

1) x₀ выбрано достаточно близко к корню уравнения f(x)=0;

2) Вторая производная не становится очень большой;

3) Первая производная не слишком близко к нулю.

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

Один из недостатков метода Ньютона состоит в том, что приходится дифференцировать функцию f(x). Заменим производную, используемую в методе Ньютона (согласно определению производной), отношением разностей:

Тогда формула примет вид:

Рассмотрим графическую интерпретацию метода. Выберем начальное приближение х₀ и рядом с ним достаточно близко возьмем точку х₁. Нередко в качестве точки х₁ берут значение . Через точки f(х₀) и f(х₁) проведем прямую – секущую. Она пересекает ось Oх в некоторой точке х₂. Вычислим координаты этой точки. Для этого воспользуемся уравнением прямой, проходящей через две точки:

Т.к. искомая точка лежит на оси Oх, то ордината этой точки, т.е. y равна нулю. Следовательно, получим следующую формулу:

а это и есть формула метода секущих.

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

Метод секущих, так же, как и метод касательных, сходится не всегда. Причины сходимости – те же, что и у метода касательных.

Метод хорд

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

Но алгоритм метода становится сложнее. Рассмотрим геометрическую интерпретацию метода.

Хорда, проходящая через точки (a, f(a)) и (b, f(b)), пересекает ось Ох в точке с. Координату точки с можно определить, используя уравнение прямой, проходящей через две точки: .

Формула метода хорд такая же, как и в методе секущих. Но, в отличие от метода секущих, где все получаемые приближения лежат по одну сторону от корня, в методе хорд получаемое приближение всегда лежит между двумя предыдущими! Следовательно, необходимо проверять на каком отрезке - [a, c] или [c, b] лежит искомый корень. Для этого достаточно проверить произведение значений функции на концах получившихся отрезков (см. отделение корней): корень есть, если данное произведение меньше нуля.

Далее выбираем тот из отрезков, на котором содержится корень. В нашем случае – это отрезок [c, b].

Переименуем один из концов отрезка так, чтобы опять получился отрезок [a, b]. Найдем новое значение с и буде повторять процесс до тех пор, пока не будет достигнута требуемая точность.

Блок-схема метода:

Метод половинного деления

Метод хорд можно сделать проще. Так как точка с – это точка лежащая между a и b, ее координаты можно определить иначе – поделить отрезок [a, b] пополам: .

Если f(x)?0 (что наиболее вероятно), то возможны два случая: либо f(x) меняет знак на отрезке [a,c], либо на отрезке [c,b]. Выбирая в каждом случае тот из отрезков, на котором происходит смена знака функции, и, продолжая метод половинного деления дальше, можно дойти до сколь угодно малого отрезка, содержащего корень уравнения. Т.е., процесс будем продолжать до тех пор, пока не будет достигнута требуемая точность: .