Раздел: Документация
0 ... 87 88 89 90 91 92 93 ... 177 В случае функции polyroots TOL имеет всегда одно и то же значение — порядка i 0~12. М ы же напишем реализующую метол Лаггера программу так, что значение T0L можно будет задавать произвольно. Формула Лаггера дает возможность найти только один корень полинома исходя из данного приближения. Чтобы найти другие корни, необходимо повторять процесс при иных значениях приближений. Однако на практике этот путь, ввиду его неэффективности, не используют. Действительно, так как заведомо неизвестно, какое приближение какой корень даст, можно многие тысячи раз впустую прокрутить алгоритм, получая один и тот же корень. Более технично, найдя корень, разделить полином на соответствующий ему линейный множитель. При ятом будет Получен полином на единицу меньшей степени, чем исходный полином. К этому полиному нужно повторно приметить алгоритм Лаггера (начальное приближение менять не обязательно). Получив второй корень, делим полином на соответствующий ему линейный множитель. И так до тех пор, пока все корни не будут найдены. Итак, прежде чем реализовыватъ непосредственно алгоритм Лаггера, нужно создать функцию, посредством которой можно будет делить полиномы на соответствующие найденным корням линейные множители. Чтобы это сделать, необходимо вспомнить, как производится деление полинома на полином «столбиком*. В общем, полином делится иа полином по тем же правилам, что н число на число. Покажем это на примере деления полинома четвертой степени па его линейный множитель: х-1Ох+35х]-50х+24х-4 х-Ах1и-бх+Пх-б -6хЧ35х-50х+34 -6x+24xJ 11хг-50х+24 11х-44х -6х+24 " -6х+24 О Как видите, поделить полипом на его линейный множитель очень просто. Соатветствем-но, несложно написать И выпол няющую эту операцию программу. Представлять полином для этой функции наиболее удобно в той же форме, что и для функции polyroots: вектора коэффициентов. Вторым параметром данной функции будет корень полинома а, на соответствующий которому линейный множитель необходимо разделить полином. pol dev(V,B); □ i- lasi(v) г<- V к Vsnbraatrix(V,0,n - 1,0,0) for i б n - 1.. О V:=(-126 -31 77 -17 1) pol dev(V,7)T = (18 7 -10 1) x4-17x3 + 77-x2-31-x-126 simplify- х3-10-х2+7х+18 g + га Программа, реализующая метод Лаггера, будет довольно сложна. Поэтому имеет смысл описать ее создание поэтапно. Назовем мы пашу щюграмму LaGuerra. В качестве параметров она будет принимать вектор коэффициентов полинома V и уровень необходимой точности TOL LaGuenaCV.TOU- В первую очередь на основании вектора коэффициентов V нужно задать функцию полинома Р. Затем необходимо объявить использующиеся в формуле Лаггера функции С и Н.Так как в выражениях функций G и Н функция Р присутствует в знаменателях дробен,то крайне важно iгредусмотреть возможность возникновения оишбки деления на нуль. Чтобы данная ошибка не вызвала сбой в работе программы, нужно сделать так, чтобы функция полинома Р никогда не была равна 0. Для этого необходимо отслеживать значение Р. Если Р окажется равным 0, в качестве значения функции следует возвратить очень м ал у ю, однако отличную от 0 величину. Логичным шагом будет увязать данную величину и 7VJL (к примеру, как 0.ITOL). Технически описанный механизм проще всего реализовать, используя функцию if. Данная функция но своему назначению аналогична конструкции if-otherwise и, соответственно, она принимает три параметра. Первый параметр — это некоторое условие. Второй параметр — величина, кото-рад должна быть возвращена, если условие окажется истинным. Третий параметр — значение, которое следует возвратить, если условие даст ложь. bst(V) / \ las((V) P(V,x)+-if £ (VyxJ.tO. £ (VjVJ. 0.1-TOL G(V,x) -P(V,x) dx j =0 ,H(V,x) 2 dx GfV.x) - P(V,x) P(V,x)P(V,x) Далее нужно создать цикл, на каждом обороте которого будет вычисляться один корень. Соответственно, количество итераций, совершаемых данным циклом, должно быть равно степени полинома. for t € 0.. last(V) - 1 Перейдя к нахождению очередного корня, нужно задать начальное приближение а. Чаще всего не имеет значения, что это будет за приближение. Однако н случае комплексных корней оно может влиять иато, сойдется алгоритм пли нет. Чтобы исключить предвзятость, будем задавать начальное приближение случайным образом в интервале от -100 до 100, используя оператор равномерно распределенных случайных чисел rnd. Задав а, необходимо объявить еще две переменные. Переменная будет хранить значение предыдущего приближения. Изначально ой можно присвоить любое значение, заметно отличающееся от а. Неременная к — это счетчик итераций, совершенных при поиске корня. Первоначально она должна быть равна 0. г а «- -100+ md(200),a,ast «- 2-в,к+- 0 Теперь следует создать цикл, который будет реализонынать итеративный механизм постепенного приближения к корню по формуле Лаггера. Так как количество необходимых итераций заведомо неизвестно, нужно использовать цикл white. В качестве условий его остановки необходимо задать то, что значение пол миома в точке приближения по модулю должно быть меньше T0L, а также разность между данным и предыдущим приближениями по абсолютной величине должна не превышать TOL while -(Р(У,ая<ТОЬла -ajTOL) i Как уже указывалось выше, в большинстве случаев не имеет значения, какое число взять в качестве начального приближения Но изредка встречаются и исключения (некоторые комплексные корни). Поэтому метод Лаггера может и не сойтись. При этом нужно сменить начальное приближение н осуществить попытку определения корня заново. Судить о том, что последовательность приближений К корню не сход1ггся, можно по величине счетчика итераций к. Так как скорость сходимости метода Лаггера очень высока, то даже прн самом малом значении TOL и самом неудачном выборе начального приближения на то, чтобы найти корень, не должно уйти больше, чем несколько десятков итераций. Если же значение к превысит установленный лимит, то нужно сгенерировать новое приближение, обнулить переменные к и а,, после чего перейти на новую итерацию посредством оператора continue. Если же значение к невелико, следует ггросто увеличить его на 1, зафиксировав очередную итерацию. if к > 100 а <- -100+ rod(200),a [ast <- 2я,*4- 0 continue к •*- к + 1 otherwise Далее нужно написать код, который будет, используя формулу Лаггера, на основании текущего приближения находить приближение следующее. Величина же старого приближения будет присваиваться переменной а. n <- last(V).Ga4- Q(V(a),Hfl 4- HfV.a) т% «- Ga + J(n - l)-(o-Ha - Са2),т, <- Ga - J(o - 1)(в H, - G,2) и lastirnaxfrn) * 0,maxH,0.1TOL) В приведенном фрагменте кода есть два неочевидных момента. Во-первых, нужно ответить на вопрос,зачем создастся массив т. Это необходимо, чтобы минимальным количеством кода определить, при каком знаке перед корнем выражение знаменателя дроби из формулы Лаггера примет максимальное значение. Занося оба варианта в массив т, мы можем определить, какой нз них больше посредством функции max. Во-вторых, нужно предусмотреть то, что наибольший элемент массива m может быть и нулем. Чтобы избежать ошибки деления на нуль, действуем точно так же, как 8 случае локальной функции Р. 0 ... 87 88 89 90 91 92 93 ... 177
|
