Гурский Д., Турбина Е. - Вычисления в MathCad 12 (1077322), страница 63
Текст из файла (страница 63)
В первую очередь, стоит отметить высокуюэффективность алгоритма Риддера: на то, чтобы найти решение с точностью до 14 знаков мантиссы, понадобилось всего семь итераций. Стандартная же точность в четырезнака мантиссы потребует всего двух оборотов алгоритма. Также обратите внимание272 •Плавав. Решение уравнений и систем уравненийна то, что каждая итерация действительно увеличивает точность на две значимые цифры. Так, например, если алгоритм проделывает шесть оборотов, ошибка проявляетсяв 12-м знаке мантиссы.
Однако нельзя достигнуть предельной точности в 16 знаков мантиссы, выполнив 8 или больше итераций. Это связано с погрешностью при проведенииарифметических операций, вычислении значений функций, приближенности при представлении бесконечных дробей, иррациональных чисел и математических констант.Код функции Ridder несложен. В нем есть только два неочевидных момента.• Оборвать работу цикла нужно тогда, когда приближение будет соответствоватькритериям сходимости к корню. По идее, эта проверка должна осуществлятьсяв заголовке цикла.
Однако тут есть одна проблема. Дело в том, что приближение вычисляется кодом, относящимся к блоку цикла. Это означает, что на момент первойитерации никакого приближения еще нет. Соответственно, проверка условия сходимости к корню вызовет ошибку. Преодолеть эту проблему можно несколькимиспособами. Во-первых, можно вычислить первое приближение до вступления в работу цикла. Однако при этом алгоритм станет менее изящным и компактным. Вовторых, можно запустить бесконечный цикл, оборвав его работу посредством оператора return в тот момент, когда приближение достигнет необходимой точности.Именно такой прием используется в программе Ridder. Чтобы сделать цикл бесконечным, в его правый маркер нужно ввести условие, которое всегда вычисляется в истину. Или же, проще, можно ввести в правый маркер 1 (в Mathcad, если условие истинно, операторы сравнения и логические операторы возвращают 1).В универсальных С-подобных языках проблема, описанная выше, решается прощеблагодаря наличию оператора цикла do-while.
Отличием этого цикла от цикла whileявляется то, что на первой итерации сначала выполняется код в блоке цикла, а ужзатем проверяется условие в заголовке.• Приближение считается достигшим нужной точности, если I f(r)| <TOL и I r-r a J <TOL.Однако возможна такая ситуация, что приближение г совпадет с корнем. При этомпроверка комплекса условий сходимости может дать ложь, так как не выполнитсяусловие для близости двух последних приближений. Дальнейшая же работа алгоритма станет невозможной, так как функция не будет принимать значения разныхзнаков на границах интервала.
Чтобы этого избежать, необходимо дополнительноосуществлять проверку на точное попадание приближения в точку корня:return (r n) if (| f(r)| < TOL л | г - r p r e v< TOb) V f(r) = ООбратите внимание на то, что комплекс критериев сходимости к корню долженбыть взят в скобки, так как он должен быть рассмотрен как единое целое.Методы ложного положения и Риддера сходятся быстрее метода Больцано.
Однакоони зависят от вида функции и поэтому менее универсальны. Существуют функции,поиск нулей которых займет у методов Regula Falsi и Риддера существенно большевремени, чем уйдет на решение этой задачи у метода Больцано. Такими функциямичасто являются функции со сложным поведением: имеющие множественные экстремумы, разрывы или очень быстро изменяющиеся в окрестности корня. А возможно лисочетать в одном методе высокую сходимость метода Риддера и универсальность метода Больцано? В принципе, да. Стратегия следующая. Используем прием, обеспечивающий высокую сходимость до тех пор, пока он оправдывает себя.
При возникновении сложностей переходим к методу бисекции, сходящемуся медленно, но устойчиво.Методом, наиболее эффективно использующим описанную стратегию, является методБрента (Brent). Данный метод применяется функцией root в том случае, если за опре-8.1. Решение уравнений• 273деленное количество итераций приближение к корню не будет получено методом Риддера.На начальном этапе поиска корня метод Брента действует точно так же, как метод Риддера.
То есть через точки (an, f(an)), (bn, f(bn)), (cn, f(cn)) (где ап и bn — границы интервала локализации корня, сп — средняя точка интервала) проводится интерполирующаяфункцию парабола. Для этого записывается соответствующий полином Лагранжа.Формула Лагранжа интенсивно применяется при разработке численных методов, таккак она позволяет автоматически записать полином степени N, проходящий через N+1известную точку. В случае метода Брента полином Лагранжа будет иметь следующий вид:Pn(x) =f(a)-(x-b)-(x-c)(a-b)-(a-c)+fl;b)(x-a)(x-c)+(b-a)-(b-c)f(c)-(x-a)-(x-b)(c-a)-(c-b)Приближением к корню считается точка, в которой полином пересекает ось X.
Найтиее можно, положив Рп(х)=0 и решив полученное уравнение. Результатом будет довольно объемное выражение, сократить которое можно, введя следующие замены:%Ъ)ЦЪ)Ка)~ f(c)~ f(a)~ Дс)Р = S-[T-(R - Т)-(с - Ь) - (1 - R)-(b - а) ]Q = (Т - 1 ) ( R - 1)-(S - 1)С учетом замен формула для вычисления приближений примет вид:х Ь+QПосле вычисления приближения проверяется, достаточно ли оно близко к корню.
Еслинет, то интервал локализации корня сужается посредством замены приближением тойграницы, которая имеет с ним один и тот же знак.Квадратичная интерполяция хорошо работает, если функция гладкая. Если же на промежутке имеются экстремумы, то приближение, вычисленное по приведенной вышеформуле, может оказаться за пределами интервала локализации корня.
В этом случаев методе Брента «плохое» приближение отбрасывается, а новое приближение вычисляется так же, как в методе бисекции. Кроме того, метод бисекции будет использован,если окажется, что вычисленное с помощью квадратичной интерполяции приближение не сужает интервал локализации корня в достаточной степени.Сделаем выводы.
Метод Брента сочетает в себе универсальность и стабильность метода Больцано и высокую сходимость метода Риддера. Это делает его одним из наиболееэффективных методов среди методов численного решения уравнения. Именно поэтому использующая его функция root так редко дает сбои.Главная сложность в использовании методов интервалов локализации корня состоитв том, что нужно определить, на каком промежутке находится корень. Причем функция на границах промежутка должна принимать значения с разными знаками (поэтому корни типа касания такими методами найдены быть не могут), она должна бытьнепрерывной, на промежутке должен быть только один корень.
Это серьезные ограничения, но если удовлетворяющий им интервал будет найден, то за определенное количество итераций (может быть, очень большое) численный метод со 100%-ной вероятностью сойдется к корню. Поэтому методы интервалов локализации корня называютглобально сходящимися.
В отличие от них методы вроде метода секущих, Мюллера2 7 4 •> Глава 8. Решение уравнений и систем уравненийили Ньютона (о них мы поговорим чуть ниже) являются локально сходящимися. Этоозначает, что то, сойдется метод к решению или нет, очень сильно зависит от выбораначального приближения. В этом они уступают глобально сходящимся методам. Скорость же сходимости лучших методов интервалов локализации корня вроде методаРиддера или метода Брента близка к скорости сходимости метода секущих и лишь немного уступает скорости сходимости метода Мюллера.
Поэтому, если корень не имеет особенностей, для его определения лучше использовать метод Риддера или метод Брента.Однако есть несколько ситуаций, в которых от использования методов интерваловлокализации корня лучше отказаться. Во-первых, корню может соответствовать непересечение функцией оси X, а лишь ее касание. Во-вторых, таким образом нельзяопределять комплексные корни. В-третьих, методы вроде метода Больцано неудобноиспользовать, если процесс решения уравнения является частью более сложной вычислительной схемы, реализованной в виде программы.
Во всех этих случаях лучше применять методы, отличительной особенностью которых является то, что они основываются на приближении к корню, а не на интервале его локализации. Этим методамсоответствует другая форма функции root, имеющая только два аргумента (имя функции и переменной). Приближение к корню присваивается переменной выше функцииroot (см. пример 8.13).Пример 8.13. Численное решение уравнения при наличии точкиприближения к корнюЗадаем функцию, описывающую уравнение, и находим точное значение первого положительного корня.f(x):=cos(2x+l)cos(2x+l) = 0solve,x -» — + --л— + --п float,20 -> .2853981633974483092424Задаем начальное приближение и ищем корень при различных значениях TOL.х:=0.2TOL:=10~ 5root(fi»,x) =0.285394105343086TOL:=10"10root(f(x),x)= 0.285398163399349Функция root с двумя аргументами по умолчанию ищет корни посредством метода секущих.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
