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

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

Для того чтобы ускорить процесс сходимости метода простых итераций (МПИ) для решения нелинейных уравнений применяют последовательности, получаемые с помощью несложных арифметических манипуляций над несколькими членами последовательности , k = 0,1,2,…. Где - функция, связанная с f(x) таким образом, что последовательность сходится к единственному корню уравнения f(x).

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

Рассмотрим два таких метода ускорения сходимости последовательности . Наличие неподвижной точки о и дифференцируемость функции ц(x) далее всюду предполагается.

4.1.  Метод Эйткена (Д2 – процесс Эйткена).

Пусть - последовательность, получаемая по формуле

               (4.1)

И при условии её сходимости корень уравнения равен (с учётом погрешности)

                (4.2),

тогда вычитая (4.1) из (4.2), имеем

а уменьшив здесь индекс на единицу, получаем

.

К  правым частям этих равенств применим формулу Лагранжа, согласно которой найдутся точки ck и ck-1 такие, что

и

       .

       Таким образом, имеют место следующие связи между ошибками соседних приближений:

       ,

Предположим, что в той окрестности корня о, в которой находятся точки xk-1 и xk, производная меняется не очень быстро. Это допущение позволяет считать, что

, где з – некоторое число,

и значит,

,  .

Беря отношение этих приближённых равенств, избавляемся от з:

       ,                                (4.3)

и разрешаем полученное приближённое уравнение относительно о:

       .

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

       .

Более коротко это записывается так:

       ,                (4.4)

где - так называемые конечные разности первого и второго порядков соответственно. Отсюда название (4.4) Д2 – преобразование или Д2 – процесс Эйткена.

       Примером реализации такого метода может служит следующий алгоритм.

Д2 – алгоритм Эйткена

Шаг 0. Ввод x0 (начального приближения), ц(x) (исходной функции), q (оценки модуля производной), е (допустимой абсолютной погрешности).

Шаг 1. Вычисление значений .

Шаг 2. Д2 – ускорение: .

Шаг 3. Вычисление контрольного значения: .

Шаг 4. Проверка на точность: если , то положить , вычислить и вернуться к шагу 2.

Шаг 5. Положить (с точностью до е).

       Применяя метод Эйткена, не следует забывать о проблеме своевременного прерывания счёта из-за потерь точности при вычитании близких чисел. Подключение Д2 – ускорения на ранней стадии МПИ, когда x0 далеко от о, может привести к расходимости процесса, по крайней мере, в случае, когда .

Метод Вегстейна.

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

Пусть уже найдены: - элемент строящейся здесь последовательности, и - точка, соответствующая одному шагу МПИ, применённого к точке . Независимо от того, сходится начатый с МПИ  (рис. 4.1, где ) или расходится (рис. 4.2 с ), отрезок AB, параллельный оси Ox и имеющий концами точки и , можно разделить точкой С так, чтобы она принадлежала прямой x = о (при этом во втором случае речь идёт о делении отрезка внешним образом) .

Рис. 4.1, 4.2. К построению метода Вегстейна.

При любых комбинациях направлений возрастания и выпуклости графика функции y=ц(x) в окрестности неподвижной точки о имеет место равенство длин отрезков BC = PC. Различаются два случая: когда и когда . По формуле Лагранжа соответственно имеем

или

.

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

       .

Разрешая это линейное уравнение относительно о, находим

.                        (4.5)

Если бы значение было известно, то тем самым задача о неподвижной точке x=ц(x) была бы решена точно. Заменим это неизвестное значение аппроксимирующим его разностным отношением:

.

Подставляя приближённое значение в (4.5), вместо корня о получаем приближение к нему

.                (4.6)

Эта итерационная формула, где k = 1,2,3,…, совместно с формулой

               (k = 0, 1, 2, …)                (4.7)

и начальными значениями полностью определяет метод Вегстейна для задачи x=ц(x) .

Значение , получаемое по формуле Вегстейна (4.6) при заданных начальных значениях и , совпадает со значением , вычисляемым Д2 – процессом Эйткена. Далее, т. е. при k ≥ 2, процессы (4.4) и (4.6) различаются. Учитывая, что МПИ является составной частью метода Вегстейна, в случаях, когда , можно заканчивать процесс вычислений, как и в методе Эйткена.

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

Алгоритм Вегстейна.

Шаг 0. Ввод x0 (начального приближения), ц(x) (исходной функции), q (оценки модуля производной), е (допустимой абсолютной погрешности).

Шаг 1. Вычислить ; положить .

Шаг 2. Вычислить .

Шаг 3. Проверить на точность: если , то вычислить ; переприсвоить значения и вернуться к шагу 2.

Шаг 4. Положить (с точностью е).

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

,

имеющая несколько отличную от (4.6) структуру.

Следующие два метода т являются обобщениями способа Ньютона для приближённого решения уравнения.

4.3.  Метод Чебышева.

Требуется найти вещественный корень уравнения f(x) = 0, изолированный в интервале (a, b). Функция f(x) предполагается непрерывной вместе с производными до n-го порядка включительно, причём в интервале (a, b) . Рассмотрим кривую . Распорядимся параметрами о, A1, A2, …, An так, чтобы кривые y=f(x) и в точке с абсциссой x0 из интервала (a, b) имели касание n-го порядка. Говорят, что кривые y=f(x) и y=ц(x) в точке с абсциссой x0 имеют касание n-го порядка, если

Геометрически точка касания n-го порядка является предельным положением (n+1) точек пересечения кривых y=f(x) и y=ц(x) при стремлении этих точек пересечения к точке с абсциссой x0. В данном случае кривая y=ц(x) неявно определяется уравнением .

При таком выборе параметров о, A1, A2, …, An за приближённое значение искомого корня можно принять абсциссу точки пересечения кривой с осью Ox, т. е. число о.

Если n=1, то (способ Ньютона).

Если n=2, то .                        (4.8)

Если n=3, то        (4.9)

Если n=4, то

(4.10)

Приведём оценки погрешности значений корней, найденных по формулам (4.8) и (4.9).

Для формулы (4.8) при n=2

.

Для формулы (4.9) при n=3

.

4.4.  Метод Данко.

Для отыскания действительного корня уравнения f(x)=0, изолированного в интервале (a, b), рассматривается кривая

               (4.11)

имеющая с кривой y = f(x) в точке с абсциссой x0 (a<x0<b) касание n-го порядка. Примем за приближённое значение корня абсциссу точки пересечения этой кривой с осью Ox, т. е. .

       Из условия касания находим это приближённое значение:

       ,                (4.12)

где

       

       .

       Если n=1, то уравнение (4.11) определяет прямую линию и для приближённого значения корня получается формула способа Ньютона.

       Таким образом, формула (4.12) обобщает способ Ньютона для приближённого решения уравнений.

       Если n=2, то 

.                (4.13)

       Если n=3, то

                       (4.14)