Раздел: Документация
0 ... 83 84 85 86 87 88 89 ... 177 Г = С 4 д)-"8°(гУ-п)) После нахождения приближения, проверяется, соответствует ли оно используемым критериям сходимости к корню (в Mathcad это I f(rn) <T0L). Если нет, то осуществляются стандартные для всех методов тггервалов локализации корня шаги. А именно: приближением заменяется та граница интервала (ап, Ьп), которая имеет с ним один и тот же знак. После этого алгоритм переходит на новую итерацию. Выведенное Риддером уравнение имеет несколько замечательных свойств. Во-первых, приближение всегда оказывается внутри интервала (ал, Ьп). Во-вторых, вычисленная на основании него последовательность приближений сходится довольно быстро. Каждое последующее приближение будет в среднем на две значимые цифры более точным по сравнению с предыдущим. В-третьих, метод Риддера очень устойчив. Реализовать метод Риддера на языке программирования Mathcad несложно. Напишем соответствующий алгоритм так, чтобы в качестве результата он возвращал не только приближение к корню, но и число, показывающее, за сколько итераций было найдено решение. Это необходимо для объективной оценки эффективности программы. Ridder(f,a,b,TOL);= error(BBad Interval!") if gign(a)= Bign(b) v fl» = 0v fl[b)=0 n«-t>) Vprev > while 1 с «- (a + b) * 2 г *r- с + (с - a) fr-2 HO - №Ш return (r n) if (ft:r) <TOLa r-rprev <TOL)v Дг) =0 b «- г if eign(a) * sign(r) a <- г otherwise p re v г о n + l) Решим с помощью написанной программы уравнение с очевидным корнем при разном значении T0L: :*х3-1 Ridder(f,0,4,10*3)=(1.00000468261462 3) Ridder(f,0,4,10"5)=(1.00000009556532 4) Ridder(f,0l4,10~8)={l.0000O0000039S б) Ridder,0,4,10"]0)=(l,000000000000817) Проанализируем полученные результаты. В первую очередь, стоит отметить высокую эффективность алгоритма Риддера: на то. чтобы найти решение с точностью до 14 знаков мантиссы, понадобилось всего семь итераций. Стандартная же точность в четыре знака мантиссы потребует всего двух оборотов алгоритма. Также обратите внимание на то, что каждая итерация действительно увеличивает точность на две значимые цифры. Так, например, если алгоритм проделывает шесть оборотов, ошибка проявляется в 12-м знаке мантиссы. Однако нельзя достигнуть предельной точности в 16 знаков мантиссы, выполнив 6 или больше итераций. Это связано с погрешностью при проведении арифметических операций, вычислении значений функций, приближенности при представлении бесконечных дробей, иррациональных чисел и математических констант. Код функции Ridder несложен. В нем есть только два неочевидных момента. □Оборвать работу цикла нужно тогда, когда приближение будет соответствовать критериям сходимости К корню. По идее, эта проверка должна осуществляться в заголовке никла. Однако тут есть одна проблема. Дело в том, что приближение вычисляется кодом, относящимся кблоку цикла. Это означает, что на момент первой итерации никакого приближения еще нет. Соответственно, проверка условия сходимости к корню вызовет ошибку. Преодолеть эту проблему можно несколькими способами. Во-первых, можно вычислить первое приближение до вступления в работу цикла. Однако при этом алгоритм станет менее изящным и компактным. Во-вторых, можно запустить бесконечный цикл, оборвал его работу посредством оператора return в тот момент, когда приближение достигнет необходимой точности. Именно такой прием используется в программе Ridder. Чтобы сделать цикл бесконечным, в его правый маркер нужно ввести условие, которое всегда вычисляется в истину. Или же, проще, можно ввести в правый маркер I (в Mathcad, если условие истинно, операторы сравнении и Логические операторы возвращают 1). В универсальных С-подобных языках проблема, описанная выше, решается проще благодаря наличию оператора цикла do-while. Отличием этого цикла от цикла while является то, что на первой итерации сначала выполняется код в блоке цикла, а уж затем проверяется условие в заголовке. □Приближение считается достиниим нужной точности, если! {(г$ <Т01 н г-г J <T0L Однако возможна такая ситуация, что приближение г совпадет с корнем. При этом проверка комплекса условий сходимости может дать ложь, так как не выполнится условие для близости двух последних приближений. Дальнейшая же работа алгоритма станет невозможной, так как функция не будет принимать значения разных знаков на границах интервала Чтобы этого избежать, необходимо дополнительно осуществлять проверку паточное попадание приближения в точку корпя: Обратите внимание на то, что комплекс критериев сходимости к корню должен быть взят в скобки, так как он должен быть рассмотрен как единое целое. Методы ложного положения и Риддера сходятся быстрее метода Больцано. Однако они зависят от вида функция н поэтому менее универсальны. Существуют функции, поиск нулей которых займет у методов Regula Falsi и Риддера существенно больше времени, чем уйдет на решение этой задачи у метода Больцано. Такими функциями часто являются функции со сложным поведением: имеющие множественные экстремумы, разрывы или очень быстро изменяющиеся в окрестности корня. А возможно ли сочетать в одном методе высокую сходимость метода Риддера и универсальность метода Больцано? В принципе, да. Стратегия следующая. Используем прием, обеспечивающий высокую сходимость до тех пор,, пока он оправдывает себя. При возникновении сложностей переходим к методу бисекции, сходящемуся медленно, но устойчиво. Методом, наиболее эффективно использующим описанную стратегию, является метод Брента (Brent). Данный метод применяется функцией root в том случае, если за олре- retura (г п)  деленное количество итераций приближение к корню не будет получено методом Риддера. На начальном этапе поиска корня метод Брента действует точнотак же, как метод Риддера, То есть через точки {ап, f(an)), (bn, РСЬр)), (ся, ft)) (где яд и Ьв — границы интервала локализации корня, сп — средняя точка интервала) проводится интерполирующая функцию парабола. Для этого записывается соответствующий полином Лагранжа. Формула Лагранжа интенсивно применяется при разработке численных методов, так как она позволяет автоматически записать полином степени N, проходящий через N+1 известную точку. В случае метода Брента полином Лагранжа будет иметь следующий аил; ft»(x-b>(x-c) tXb)(x- аНх-с) ВДЧх- а)-(х-Ь) Рп(х) =-+-+- (а - Ь)-(а - с) (Ь - а)(Ь - с)(с - а)-(с - Ь) Приближением к корню считается точка, в которой полином пересекает ось X. Найтн ее можно, положив Ря(х)-0 и решив пол ученное уравнение. Результатом будет довольно объемное выражение, сократить которое можно, введя следующие замены: «ь) т ад Р = S[T(R - Т).(с - Ь) - (1 - R)(b - а) ]Q - (Т - ))-fR - 1)-(S - 1) С учетом замен формула для вычисления приближений примет вил: t Р Q После вычисле