- •Введение
- •1 Средства для решения задач нелинейных алгебраических уравнений в распределенной вычислительной среде
- •1.1 Понятие распределенных вычислений как способа решения трудоёмких вычислительных задач с использованием нескольких компьютеров
- •1.2 Распределенные вычисления на основе стека
- •1.3 Понятие клиент-серверных систем
- •1.4 Методы и их модификации для решения систем нелинейных уравнений
- •2 Алгоритмы и методы для решения нелинейных алгебраиеских уравнений на основе метода натуральных градиентов
- •2.1 Техническое задание для написания программы для решения систем нелинейных алгебраических уравнений методом натуральных градиентов
- •2.2 Aлгоритм метода натуральных градиентов
- •2.3 Алгоритмы линейного и распределенного решения
- •2.4 Алгоритм синтаксического анализатора, разработанного на основе обратной польской записи
- •2.5 Математическая модель распределенного вычисления Якобиана отображения
- •2.6 Описание основных функций клиент-серверного приложения
- •3 Программный комплекс для решени нелинейных алгебраических уравнений методом натуральных градиентов
- •3.1 Руководство пользователя
- •3.2 Результат исследование зависимости времени нахождения решения от размерности системы и способа решения
- •Заключение
- •Список использованных источников
- •Приложение а
- •Код сервеной части
- •Приложение б
- •Код клиенткой части
- •Приложение в
- •Данные из тестовых файлов
- •Приложение г
2.4 Алгоритм синтаксического анализатора, разработанного на основе обратной польской записи
Рассмотрим систему нелинейных уравнений (2.4), заданную в текстовом формате.
x001+x001^2 -2*x002x003-0,1=0
x002-x002^2+sin(3*x001*x003)+0,2=0 (2.4)
x003+cos(x003^2)+2*x001*x002-0,3=0
Система (2.4) состоит из 3-х нелинейных уравнений и соответственно из 3-х неизвестных: x001, x002, x003. Представляя уравнения (2.4) как функции, можем записать (2.5).
f1(x001, x002, x003)=x001+x001^2 -2*x002x003-0,1
f2(x001, x002, x003)=x002-x002^2+sin(3*x001*x003)+0,2=0 (2.5)
f3(x001, x002, x003)=x003+cos(x003^2)+2*x001*x002-0,3=0
При нахождении промежуточных значений функций итерационного процесса решения системы, можно сделать следующие шаги:
− заменить в (2.4) все части x002x003 на x002*x003;
− все выражения, заключенные в скобки (x002+x003)(x066*x003) заменить на (x002+x003)*( x066*x003);
− заменить все тригонометрические функции на значения.
В результате получим в каждой строке системы выражение, состоящее из чисел и знаков простейших арифметических операций. Далее прибегая к обратной польской записи, можно вычислить значение функции при заданных значениях неизвестных итерационного процесса их уточнения.
В математике существует древняя традиция помещать оператор между операндами (x+y), а не после операндов (xy+). Форма с оператором между операндами называется инфиксной записью. Форма с оператором после операндов называется постфиксной, или обратной польской записью в честь польского логика Я. Лукасевича, который изучал свойства этой записи.
Обратная польская запись имеет ряд преимуществ перед инфиксной записью при выражении алгебраических формул:
– любая формула может быть выражена без скобок;
– она удобна для вычисления формул в машинах со стеками;
– инфиксные операторы имеют приоритеты, которые произвольны и нежелательны.
При составлении обратной польской записи рассматривается поочередно каждый символ:
а) если этот символ − число (или переменная), то просто помещаем его в выходную строку;
б) если символ − знак операции (+, -, *, / ), то проверяем приоритет данной операции. Операции умножения и деления имеют наивысший приоритет (допустим он равен 3). Операции сложения и вычитания имеют меньший приоритет (равен 2). Наименьший приоритет (равен 1) имеет открывающая скобка. Получив один из этих символов, проверяем стек:
1) если стек все еще пуст, или находящиеся в нем символы (а находится в нем могут только знаки операций и открывающая скобка) имеют меньший приоритет, чем приоритет текущего символа, то помещаем текущий символ в стек;
2) если символ, находящийся на вершине стека имеет приоритет, больший или равный приоритету текущего символа, то извлекаем символы из стека в выходную строку до тех пор, пока выполняется это условие, затем переходим к пункту 1);
в) если текущий символ – это открывающая скобка, то помещаем ее в стек;
г) если текущий символ – это закрывающая скобка, то извлекаем символы из стека в выходную строку до тех пор, пока не встретим в стеке открывающую скобку (то есть символ с приоритетом, равным 1), которую следует просто уничтожить. Закрывающая скобка также уничтожается.
Если вся входная строка разобрана, а в стеке еще остаются знаки операций, извлекаем их из стека в выходную строку. Далее необходимо вычислить выражение, записанное в обратной польской записи. Для реализации этого алгоритма используется стек для чисел (или для переменных, если они встречаются в исходном выражении). В качестве входной строки рассматривается выражение, записанное в ОПЗ:
а) если очередной символ входной строки – число, он помещается в стек;
б) если очередной символ – это знак операции, то извлекаем из стека два верхних числа, используем их в качестве операндов для этой операции, затем кладем результат обратно в стек.
Когда вся входная строка будет разобрана в стеке должно остаться одно число, которое и будет результатом данного выражения.