Символьное дифференцирование - Шаги дифференцирования
ОГЛАВЛЕНИЕ
Шаги дифференцирования
Разбор выражения для заполнения набора
Разбор выражения – процесс сканирования выражения для отыскания его элементов (чисел, операторов, функций и переменных). Каждый оператор должен иметь два операнда; например, 2*12. Оператор "*" имеет два операнда: 2 и 12. Каждая функция имеет аргумент. Например, для sin(x) функцией является sin, а аргументом - x. Надо особым образом сканировать выражение, чтобы определить каждый оператор и операнды, а также каждый аргумент функции, чтобы упростить расчет или дифференцирование.
Выполнение выражения зависит от приоритета операторов. Если построить такой набор операторов и операндов, чтобы за каждым оператором следовали его два операнда, то 2*12 построит следующий набор: "*, "2", "12". Итак, функция расчета проверяет набор. Если элемент является оператором, то функция берет два его оператора и производит расчет для них по рекурсивной формуле, чтобы вычислить все выражение. Например, выражение
sin(2*12)/7+9^2
должно вычисляться по следующим шагам:
1. Вычислить sin(2*12)/7
2. Вычислить 9^2
3. Затем применить оператор + к двум результатам
4. Чтобы вычислить пункт 1, надо:
1. Вычислить sin(2*12)
2. Вычислить 7
3. Затем поделить два результата
4. Чтобы вычислить пункт 4.1, надо:
1. Вычислить 2*12
2. Применить функцию sin к результату
3. Чтобы вычислить пункт 4.4.1, надо:
1. Применить оператор * к двум операндам 2 и 12
Сканирующая функция принимает входное выражение и массив операндов в зависимости от их приоритета, как в следующем коде:
///////////////////////////////////////////////////////////
// GetOperator: сканирует входную строку,
// чтобы найти входные операторы
///////////////////////////////////////////////////////////
int GetOperator(IN LPCSTR lpcs, IN LPCSTR lpcsOperators[])
{
for(int nIndex = 0; lpcsOperators[nIndex]; nIndex++)
{
int nOpen = 0;
// сканируется выражение с конца
LPSTR p = (LPSTR)lpcs+strlen(lpcs)-1;
// цикл сообщает о достижении начала выражения
while(p >= lpcs)
{
// проверка на закрывающую скобку
if(*p == ')')
nOpen++;
// проверка на открывающую скобку
else if(*p == '(')
nOpen--;
// проверка на оператор
else if(nOpen == 0 && strchr(lpcsOperators[nIndex], *p) != NULL)
// проверка, является ли оператор меткой знака
if((*p != '-' && *p != '+') ||
(p != lpcs && IsRightSign(*(p-1),
lpcsOperators, nIndex+1)))
// возвращается индекс оператора
return (int)(p-lpcs);
p--;
}
}
// оператор не найден
return -1;
}
Очевидно, что это рекурсивная операция. Чтобы сделать это, надо сформулировать выражение в виде набора операторов и операндов и определенным образом обработать этот набор, чтобы получить конечный результат. Основные шаги для осуществления этого таковы:
• Найти операторы
• Разбить выражение по индексу оператора
• Добавить два полученных операнда в набор
• Если операторы не найдены, проверить, начинается ли выражение с имени функции
Применение предыдущих шагов дает следующий набор:
|
+ |
||||
|
/ |
||||
|
sin(2*12) |
|
|||
|
7 |
||||
|
^ |
||||
|
9 |
||||
|
2 |
Для более подробного описания рассматривается код, разбирающий выражение и заполняющий набор:
bool FillStack(LPCSTR lpcsInput, vector<EXPRESSIONITEM*>& vStack)
{
// массив операторов от верхнего до нижнего
priority LPCSTR lpcsOperators[] = { "+-", "*/", "^%", NULL };
// вставить первый входной элемент в набор
vStack.push_back(new ExpressionItem(lpcsInput));
// цикл проходит по набору выражения, чтобы проверить,
// можно ли разбить выражение на два запроса
for(int nIndex = 0; nIndex < (int)vStack.size(); nIndex++)
// проверяет, является ли элемент выражения оператором
if(vStack[nIndex]->m_cOperator == 0)
{
// копируется строка выражения
CString str = vStack[nIndex]->m_strInput;
// выражение разбирается, чтобы найти операторы
int nOpIndex = GetOperator(str, lpcsOperators);
if(nOpIndex != -1)
{
// выражение разбивается на
// два запроса по индексу оператора
vStack[nIndex]->m_cOperator = str[nOpIndex];
// добавляется левый операнд оператора
// как новое выражение
vStack.insert(vStack.begin()+nIndex+1,
new ExpressionItem(str.Left(nOpIndex)));
// добавляется правый операнд оператора
// как новое выражение
vStack.insert(vStack.begin()+nIndex+2,
new ExpressionItem(str.Mid(nOpIndex+1)));
}
else
// проверяется, начинается ли строка выражения
// с функции или круглых скобок
if((vStack[nIndex]->m_nFunction = GetFunction(str,
vStack[nIndex]->m_nSign)) == 0
&& vStack[nIndex]->m_nSign == 0)
// удаляются круглые скобки, и выражение повторно просматривается
vStack[nIndex--]->m_strInput =
str.Mid(1, str.GetLength()-2);
}
return true;
}
Это простейший код разбора математического выражения. Его комментарии собраны по пунктам ниже:
• Вставить первый входной элемент в набор
• Цикл проходит по набору выражения, чтобы проверить, можно ли разбить выражение на два запроса
• Проверить, является ли элемент выражения оператором (+-*/^)
• Разобрать выражение, чтобы найти операторы
• Если оператор найден:
o Разбить выражение на два запроса по индексу оператора
o Добавить левый операнд оператора как новое выражение
o Добавить правый операнд оператора как новое выражение
• Иначе
o Проверить, начинается ли строка выражения с функции или круглых скобок
o Если функция найдена, установить ее номер в данных выражения
Применение формул дифференцирования к набору
Применение формул дифференцирования – значит выполнять итерации по набору, брать каждый оператор и применять правило дифференцирования (в зависимости от оператора) к двум операндам оператора:
|
Выражение |
Производная |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Если любой операнд является оператором, то функция снова вызывается рекурсивно для дифференцирования всего выражения. Следующий код представляет эту функцию:
CString DifferentiateStack(vector<EXPRESSIONITEM*>& vStack, int& nExpression)
{
ExpressionItem *pQI = vStack[nExpression++];
if(pQI->m_cOperator)
{
// взять левый операнд
CString u = vStack[nExpression]->GetInput();
// взять производную от левого операнда
CString du = DifferentiateStack(vStack, nExpression);
// взять правый операнд
CString v = vStack[nExpression]->GetInput();
// взять производную от правого операнда
CString dv = DifferentiateStack(vStack, nExpression);
if(du == '0') // u - константа
...
else if(dv == '0') // v - константа
...
else
switch(pQI->m_cOperator)
{
case '-': // d(u-v) = du-dv
case '+': // d(u+v) = du+dv
pQI->m_strOutput = '('+du+pQI->m_cOperator+dv+')';
break;
case '*': // d(u*v) = u*dv+du*v
pQI->m_strOutput = '('+u+'*'+dv+'+'+du+'*'+v+')';
break;
case '/': // d(u/v) = (du*v-u*dv)/v^2
pQI->m_strOutput = '('+du+'*'+v+'-'+u+'*'+dv+")/("+v+")^2";
break;
case '^': // d(u^v) = v*u^(v-1)*du+u^v*ln(u)*dv
pQI->m_strOutput = '('+v+'*'+u+"^("+v+"-1)*"+ du+
'+'+u+'^'+v+"*ln("+u+")*"+dv+')';
break;
}
}
else
// взять производную выражения
pQI->GetDifferentiation();
// вернуть полученную производную
return pQI->m_strOutput;
}
Оптимизация уравнения
Оптимизация уравнения включает в себя следующие простые шаги:
• Заменить "--" на "" или "+"
• Заменить "+-" на "-"
• Заменить "((....))" на "(....)"
• Удалить все "1*"
• Удалить все "*1"
• Удалить все "^1"
• Удалить все "1*"
• Удалить ненужные круглые скобки
Псевдокод дифференцирования
Differentiate(input)
{
Stack = FillStack(input)
output = DifferentiateStack(Stack)
Optimize(output)
return output
}
FillStack(input)
{
operators[] { "+-", "*/", "^%" }
stack.push(input)
loop( n = 1 to stack.size() )
{
if stack[n] is not operator
if GetOperator(stack[n],
operators) success
{
Split stack[n]
stack.Insrt(left operand)
stack.Insrt(right operand)
}
else
GetFunction(stack[n])
}
}
DifferentiateStack(stack, index)
{
if stack[index] is operator
{
index++
u = stack[index]
du = DifferentiateStack(stack, index)
v = stack[index]
dv = DifferentiateStack(stack, index)
if operator = '-' or '+'
output = du+operator+dv
else if operator = '*'
output = u*dv+du*v
else if operator = '/'
output = (du*v-u*dv)/v^2
else if operator = '^'
output = v*u^(v-1)*du+u^v*ln(u)*dv
}
else
output = stack[index++].GetDifferentiation()
return output
}
void Optimize(str)
{
replace "--" with "" or "+"
replace "+-" with "-"
replace "((....))" with "(....)"
remove any 1*
remove any *1
remove any exponent equal 1
remove unneeded parentheses
if str changed then
Optimize(str)
}
ExpressionItem::GetDifferentiation()
{
if Function then
{
arument = Argument(input);
if function = SIN
output = Differentiate(arument)*cos(arument)
else if function = COS
output = Differentiate(arument)*(-sin(arument))
else
...
}
}
else
{
if input = "x"
output = "1"
else if input = "-x"
output = "-1"
else if input is numeric
output = "0"
else
output = "d"+input+"/dx"
}
}