Методы решения нелинейных уравнений

ЛЕКЦИИ 13-14 МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙ 10.1 Метод дихотомии Целью решения системы нелинейных уравнений является вычисление базисных интенсивностей 0 q для каждого контура q . В качестве базисной обычно выбирается дуга контура q , выходящая из узла с наименьшим номером i . Анализ соотношений (9.16) и (9.20) показывает, что каждое нелинейное уравнение в области допустимых решений представляет собой монотонно возрастающую функцию. Вид зависимости n (  ) для первого нелинейного уравнения примера 9.5 представлен на рис. 10.1. 4 n 3 1   4 3 1  Рис. 10.1 Зависимость n от λ На рис 10.1 цифрам "1", "3", "4" - соответствуют номера узлов первого контура, которые описываются слагаемыми в соотношении (9.21). Знаком  обозначена вся правая часть первого нелинейного уравнения. Для решения системы нелинейных уравнений используем метод дихотомии, называемый также "метод проб". итеративный Для этого представим соотношение (9.20) в канонической форме: f ( q ) = nq - n kiq iq , (10.1) Каноническая форма нелинейного уравнения (10.1) изображена на рис. 10.2. Решению уравнения соответствует равенство: f (  q ) = 0. * f(q) nq *q B(q0) min i i  E(q0) (начало интервала) (конец интервала) (q,s) Рис. 10.2 Каноническая форма нелинейного уравнения В основу процедуры решения нелинейного уравнения положены следующие условия: 1) Если корень уравнения лежит между  =  B  B +  E )/2}. и  =  E , то вычисляют f {( Если f {(  B +  E )/2}.имеет тот же знак, что и f (  B ), то присваивают  B = (  B +  E )/2 , а  E не изменяют и повторяют процедуру вычисления f (  q ). Если f {(  B +  E )/2}.имеет тот же знак, что и f (  E ), то присваивают  E = (  B +  E )/2 , а  B не изменяют и повторяют процедуру вычисления f (  q ). Расчет продолжается до тех пор, пока на шаге s будет достигнуто условие:  qs = | f где  s 1 (  q ) - f s (  q )| / f s 1 (  q ) <  , - заданная точность вычислений. Ответственным является шаг граничных величин: sB0 и s = 0, на котором назначаются значения sEo . Для рассматриваемого типа нелинейных уравнений для каждого контура q целесообразно принимать: sB0 = 0; и sEo = min  i , где  i  q. Пример 10.1. (см.рис. 9.10) Для контура q = 1, n1=3; 1=1 1/s; 3=4 1/s; 4=3 1/s , ) для контура q = 2; n2=4; 2=2 1/s; 3=4 1/s; 4=3 1/s . Точность вычислений  = 6% По соотношению (9.11) вычисляем i: 1=0,67; 2=0,75; 3=0,86; 4=0,86 . Последовательно для каждого контура q и каждого шага s вычисляем:  B (q,s),  E (q,s), f(q,s),  q (s): s=0 s=1 B(1,0)=0; E(1,0)=1; B(2,0)=0; E(2,0)=2 ; 1(1)=0,5; 2(1)=1; f(1,1)=1,26; f(2,1)=1,22 ; B(1,1)=0,5; E(1,1)=1; B(2,1)=1; E(2,1)=2 ; s=2 1(2)=0,75; 2(2)=1,5; f(1,2)= -10,75; f(2,2)= -22,2; B(1,2)=0,5; E(1,2)=0,75; B(2,2)=1; E(2,2)=1,5; s=3 1(3)=0,62; 2(3)=1,25; f(1,3)=-0,09; f(2,3)=-0,94; B(1,3)=0,5; E(1,3)=0,62; B(2,3)=1,0; E(2,3)=1,25; s=4 1(4)=0,56; 2(4)=1,13; f(1,4)=0,72; f(2,4)=0,22; B(1,4)=0,56; E(1,4)=0,62; B(2,4)=1,13; E(2,4)=1,25. С заданной точностью  = 6% получаем, 1 = 0,59 1/s, 2 = 1,19 1/s. 10.2 Метод тангенсов для решения нелинейных уравнений В настоящее время до реализации ВС можно только примерно предсказать её будущую производительность, но организация, принимающая решение о построении сети, желает получить определённые гарантии качества, так как создание ВС требует определённых затрат. Поэтому всё большой интерес проявляется к моделированию вычислительных сетей, так как это позволяет рассчитать затраты на построение ВС до закупки оборудования и оптимально распределить средства. Так же необходимо помнить, что каждая организация обладает своей спецификой, и аппаратные средства нужно подбирать под конкретные цели и задачи. Обычно в таких случаях используют хорошо зарекомендовавшие себя решения, но это не всегда приводит к должному результату. При проектировании ВС разработчику на различных этапах необходимо генерировать варианты проектных решений, рассчитывать функциональные характеристики для каждого варианта вычислительной сети. Для повышения точности определения функциональных характеристик вычислительной сети необходимо использовать большое число параметров математической модели, которая описывает функционирование ВС. Это усложняет расчётные соотношения и увеличивает объём вычислений. Преодолеть отмеченные трудности можно посредством создания комплексной системы автоматизированного проектирования вычислительной сети. В настоящее время имеется широкая гамма отдельных методик, каждая из которых позволяет определить свой, достаточно узкий набор функциональных характеристик вычислительной сети. Учитывая, что основные требования пользователь ВС предъявляет временным характеристикам, которые являются основной оценкой качества функционирования, для определения производительности используется метод контуров, который позволяет определять именно эти параметры ВС. При применении метода контуров для расчета параметров одной из трудоемких задач (особенно для ВС большой размерности) является решение нелинейных уравнений. При достаточно большой загрузке сети методы дихотомии не обеспечивают получение гарантированного решения нелинейных уравнений, так как в знаменателе каждого слагаемого могут входить неизвестные интенсивности потоков заявок и диапазон области допустимых решений не является постоянным. Автором предложен метод тангенсов, который гарантирует сходимость при решении системы нелинейных уравнений. Этапы определения производительности вычислительных сетей, которые рассмотрены в предыдущем разделе предусматривают в соответствии с методом контуров составление и решение систем линейных и нелинейных уравнений. Нелинейные уравнения являются частью аналитической модели и составляются для каждого контура. Совместное их решение позволяет определить базовые интенсивности 𝜆0𝑞 для потоков всех контуров сети. Основой составления уравнений является условие, что в установившемся режиме количество сообщений в одном контуре не изменяется и равно сумме математических ожиданий сообщений в каждом узле данного контура. Тогда, в соответствии с (9.20), для каждого контура можно записать нелинейное уравнение (10.2): 𝑛𝑞 = ∑𝑘𝑖 𝑛𝑖𝑞 при 𝑘𝑖 , 𝑖𝑞 , 𝑛𝑖𝑞 = 𝜆𝑖𝑞 / (𝜇𝑖 − 𝛾𝑖 𝜆𝑖𝑞 ), где 𝑛𝑞 –количество сообщений в одном контуре, 𝜆𝑖𝑞 – интенсивность поступления сообщений, 𝜇𝑖 - интенсивность обслуживания сообщений в узле. При расчёте характеристик замкнутых систем необходимо использовать коэффициент ограниченности очереди: Формулировка задачи Таким образом, имеем систему из Q уравнений, (𝑞 = ̅̅̅̅̅ 1, 𝑄) с Q неизвестными базисными интенсивностями 𝜆𝑞 . Целью решения нелинейных уравнений является вычисление базисных интенсивностей 𝜆0𝑞 . Решение системы нелинейных уравнений выполняется в 2 этапа. Решение системы нелинейных уравнений выполняется в 2 этапа. На первом этапе для первого уравнения принимаем: 𝜆0𝑞 = 𝜆0𝑞=1 для всех 𝑞 = ̅̅̅̅̅ 1, 𝑄 и выполняем решение этого уравнения пошаговым 0(1) методом тангенсов и находим для (1)-ой итерации значение 𝜆𝑞=1 ’ Далее, для каждого q-го уравнения подставляем фиксированные значения: 0(1) 0(1) 0(1) 𝜆𝑞=1 𝜆𝑞=2 𝜆𝑞=𝑄−1 для уже найденных интенсивностей, принимаем 0(1) 𝜆𝑞 0(1) 0(1) для всех не вычисленных интенсивностей и находим = 𝜆𝑞+1 = = 𝜆𝑄 0(1) итерации значение 𝜆𝑞 . Вычисления 1-го этапа производятся для всех Q уравнений. Второй этап начинается после того как вычислены значения всех 0(1) 0(1) 0(1) интенсивностей 𝜆1 , 𝜆2 , 𝜆𝑄 . При решении каждого уравнения на каждой 0(2) последующей итерации определяется значение интенсивности 𝜆𝑞 соответствующей итерации, при этом значения остальных интенсивностей рассматриваются как фиксированные, численно равные значениям последних итераций этих интенсивностей. Для решения каждого нелинейного уравнения будем использовать пошаговый метод тангенсов. Для этого представим каждое нелинейное уравнение (10.2) в канонической форме: 𝐹(𝜆𝑞) = 𝑛𝑞 − ∑𝑘1 𝑛𝑖𝑞 (10.3) Каноническая форма нелинейного уравнения (10.3) изображена на рис (10.3). Решению соответствует корень уравнения при 𝐹(𝜆𝑞 ) =0 Рис. 10.3 Каноническая форма нелинейного уравнения 1) Решение одного уравнения пошаговым методом тангенса: (0) Начальной точкой итеративной процедуры (шаг s=0) является точка 𝜆𝑞 =0, в которой 𝐹(𝜆𝑞 ) = 𝑛𝑞 ; (см. рисунок 10.4). (0) На шаге s = 1 из точки 𝐹 (𝜆𝑞 )= 𝑛𝑞 проводим линию (1), наклон которой определяется коэффициентом 𝑘𝑞𝑠−1 , равным отношению 𝜆 к 𝐹(𝜆). (0) (0) (𝑠) 𝜇 Для s=0, 𝜆𝑞 = 0 ; 𝐹(𝜆𝑞 ) = 𝑛𝑞 ; 𝑘𝑞 = (min𝑖 |𝑞𝑖|) /2𝑛𝑞 , где 𝑖 𝜇𝑖 – интенсивность обслуживания сообщений в i-м узле, |𝑞𝑖 |- количество контуров в i-м узле, 𝑛𝑞 - количество сообщений в i-м контуре. На каждом s-м шаге этого этапа алгоритма используются соотношения (10.4 и 10.5) (𝑠) (𝑠−1) 𝜆𝑞 = 𝜆𝑞 (𝑠−1) Δ𝑞 (𝑠−1) + Δ𝑞 (𝑠−1) = 𝑘𝑞 (10.4) (𝑠−1) 𝐹 (𝜆𝑞 ) (10.5) В результате вычислений возможна ситуация выхода из зоны допустимых решений, признаком этого является значение 𝐹(𝜆𝑞𝑠 ) < 0. (𝑠) В этом случае необходимо применять коррекцию 𝑘𝑞 : (𝑠 (𝑠 (𝑠−1 - если 𝐹 (𝜆𝑞 ) < 0, то 𝐹 (𝜆𝑞 ) = 𝐹 (𝜆𝑞 (𝑠 (𝑠) (𝑠−1) - если 𝐹 (𝜆𝑞 ) ≥ 0, то 𝑘𝑞 = 𝑘𝑞 (𝑠) (𝑠−1) ) и 𝑘𝑞 = 𝑘 𝑞 . Сходимость метода контуров поясняется рисунком 10.4 Рис. 10.4 Пояснение сходимости итеративной процедуры /2; (10.6) 2 Решение системы уравнений 𝜇 2.1 Принимаем 0(0) 𝜆𝑞=1 = 0(0) 𝜆𝑞=2 (min |𝑞|1 ) ⁄ = … =. 2𝑛𝑞 Далее решаем все уравнения в соответствии с п. 1, и находим: 0(1) 0(1) 0(1) 𝜆𝑞=1 , 𝜆𝑞=2 , 𝜆𝑞=3 ,……. 2.2 Последовательное решение каждого уравнения: 0(1) 0(2) - берём уравнение для первого контура фиксируем 𝜆0𝑞=2 = 𝜆𝑞=2 …. и ищем 𝜆𝑞=1 в соответствии с п. 1; 0(1) - берём уравнение для второго контура фиксируем 𝜆0𝑞=1 = 𝜆𝑞=1 …. 0(2) 𝜆𝑞=2 и ищем в соответствии с п. 1; - продолжаем для всех контуров выполнять итерации 2.3 Циклически выполняем п. 2.2 пока не будет достигнута точность 𝜀. (𝑠) Условие окончания цикла: (𝑠) 𝜆𝑞 −𝜆𝑞 (𝑠) 𝜆𝑞 100% < 𝜀 Алгоритмы метода представлены на рис.10.5 и 10.6 В блок "начальные установки" входит, нахождение минимума из всех возможных интенсивностей обслуживания, что является ограничением по  для нахождения первого тангенса. Далее проверяем, для всех ли уравнений из системы найдено решение, - если для всех, то надо проверить достигyнута ли требуемая точность решения, если да – то конец решения, если нет – то решаем заново; - если не для всех, то находим  для следующего уравнения, при этом изменяется только , соответствующее данному уравнению, остальные  фиксируются. При решении одного уравнения, сначала вычисляется первый тангенс по формуле: tg  ni , min(  i ) который численно равен на начальному значению коэффициента К, определяющий крутизну первого шага ( tg  K ). 1 Начало 2 начальные установки 3 Нет 4 Нет Да contur < contur_count f=0 6 5точность достигнута при решении всех уровнений? Нет Да 7 Расчёт нелитейных уровнений Result_l [contur] Redult_frase [contur] contur = contur + 1 Нет 8 Да (result_l res_l_old) / result_l < 0,05 9 10 res_l_old = result_l f=1 11 Конец Рис.10.5 Алгоритм метода тангенсов. Далее рассчитывается  по формуле    s s 1 F (s 1 )  , K где s-1 – значение, полученное на предыдущем шаге. Да (𝑠) По полученному  рассчитывается значение функции 𝐹 (𝜆𝑞 ) Далее идёт проверка, не нарушены ли границы, в которых должно быть решение, т.е. должно выполняться условие 0 < F(s) < 𝑛𝑞 , если нарушаются границы, то К увеличивается в два раза, и по сравнению со значением предыдущего шага, наклон прямой становиться в два раза круче. Далее шаги производятся с новым углом наклона. При достижении указанной точности расчёт одного прекращается и происходит переход к следующему уравнению. уравнения Алгоритм расчёта одного нелинейного уравнения (блок 7) приведён на рис. 10.6. 1 Начало 2 вычисление новой  по tg 3 вычисление значения функции 5 Нет нарушены границы? Да 7 Нет 6 достигнута точность? расчёт нового tg  =_old f() = f(_old) Да 8 Конец Рис 10.6 Алгоритм расчёта одного уравнения Пример 10.2 В качестве примера рассмотрим простую ВС с тремя узлами и двумя замкнутыми контурами. (см. рисунок 10.7). Контур q =1 обслуживают узлы 1 и 3, контур q =2 обслуживают узлы 2 и 3. Для рассматриваемой системы необходимо рассчитать интенсивности 𝜆𝑞 поступления сообщений Рис. 10.7 ВС с двумя контурами к примеру 10.2 Для рассматриваемой ВС можно записать систему из двух нелинейных уравнений. 𝑛1 = 𝑛2 = 𝜆1,1 𝜇1 −𝛾1 𝜆1,1 𝜆2,2 𝜇2 −𝛾2 𝜆2,2 + + 𝜆3,1 𝜇3 −𝛾3 (𝜆3,1 +𝜆3,2 ) 𝜆3,2 𝜇3 −𝛾3 (𝜆3,1 +𝜆3,2 ) Принимаем следующие численные значения - для конура q = 1, n1 = 4, 𝜇1 = 10 1/с; 𝜇3 =10 1/с - для контура q = 2, n2 = 8, 𝜇2 = 10; 1/с 𝜇3 =10 1/с точность вычисления e = 0,05 Результат решения: 𝜆1 = 6.06 1/с ; 𝜆2 = 3.689 1|c шаг s 1 2 3 𝜆1 контура 1 5,0 5,5 5,86 6,06 𝜆2 контура 2 5,0 4,4 4,097 3,81 Результат сходимости алгоритма представлен на рис. 10.8. Рис. 10.8 Иллюстрация сходимости алгоритма Самоконтроль знаний Контрольные вопросы 1. Почему при решении нелинейных уравнений следует использовать итеративные методы? 2. Почему на рисунке 10.2 правая граница интервала интенсивности ΛЕ (𝑞0 ) поступления заявок-сообщений принимается равной min𝑖 𝜇𝑖 ? 3. Почему метод дихотомии не пригоден для решения системы нелинейных уравнений? 4. Каким образом обеспечивается требование равенства числа нелинейных уравнений количеству базовых интенсивностей 𝜆𝑞0 ? 5. Как задаются начальные значения базовых интенсивностей 𝜆𝑞0 на первом и втором этапах метода тангенсов? Контрольные задания 1. Для примера 10.2 выполнить расчет с заданной точностью 𝜀 = 10%. 2. Различаются ли между собой коэффициенты k для разных контуров и почему? 3. Объяснить, почему интенсивность 𝜆0𝑞=2 > 𝜆0𝑞=1 и почему?