在手机上绘制根轨迹

写了一个能够绘制线性系统根轨迹、响应曲线、计算幅值裕度、相位裕度等的手机APP。下载地址在文末。

本文公式较多，在浏览器中将会花较长时间用于渲染公式。

算法

各种裕度的计算

很简单，就是用弦截法计算各种穿越频率，然后计算裕度。具体的代码以及API设计可以见GitHub，不过弦截法需要给出猜测初值，在手机里这个程序也就只能在几个初值里面试，如果这个初值迭代不收敛就换另一个初值。目前的算法能够通过所有我写的测试用例，不过不知道是否有不对的情况。

与绘制各种根轨迹相关的算法

多项式求根算法

非常美妙的事情是，NDK虽然是个大坑，不过Eigen库还是能够使用的。
多项式的求根可以转化为它的companion matrix的特征值问题来求解：
$p(t)=c_{0}+c_{1}t+\cdots +c_{n-1}t^{n-1}+t^{n}$的companion matrix是
$\begin{equation} \tag{a} C(p)=\begin{bmatrix} 0 & 0 & \dots & 0 & -c_{0}\\ 1 & 0 & \dots & 0 & -c_{1}\\ 0 & 1 & \dots & 0 & -c_{2}\\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \dots & 1 & -c_{n-1} \end{bmatrix} \end{equation}$ 这样就可以将多项式求根问题转化为矩阵的特征值问题，然后利用Eigen库求解。

排序算法

由于Eigen求出特征值是无序的，而绘图时是按照方程的根的离散点连线绘制，因此可能会造成各条轨迹交织的情况。为了避免这种情况，需要对根进行排序，即这组点到上组点的距离分别最近进行排序。这个没有想到更好的点子，实现的算法复杂度为$O(n^2)$，但是在手机上没有卡过，代码如下：

for(int i = 0; i < matsz; ++i){
    std::swap(res[i], *std::min_element(res.begin() + i,res.end(),
    [&i](std::complex<double> &a, std::complex<double> &b)   
    // static variables don't need to be captured
    {return norm(a - pre[i]) < norm(b - pre[i]);}));
    pre[i] = res[i];
}

计算响应的算法

这个一开始想用矩阵的幂来进行计算，但是发现许多时候线性系统的$\mathbf{A}$矩阵都是奇异的，没办法，还是只能用RK45算法，好在现在手机处理器性能很强，没有任何卡的迹象。

处理用户输入

为了让用户能够有更好的交互体验，设计的输入格式比较宽送。处理用户输入用了Boost::tokenizer库，这是一个Header-only的库，不需要编译（当然我也自己编译了Boost库，除了Math库编译不了，别的都可以编译，具体能不能用还没有认真试过）。NDK真的是一个大坑，GOOGLE官方对GCC值支持到GCC4.9，然而Qt for Android是GCC编译的，而GCC4.9对C++14支持不全不说，有的C++11的东西都没法用，比如std::stod,std::to_string，所以先自己实现一个。。。

#ifdef FOR_MOBILE
namespace std {

    template <typename T>
    std::string to_string(T value)
    {
        std::ostringstream os ;
        os << value ;
        return os.str() ;
    }

    //template <typename T>
    double stod(const std::string& str)
    {
        double res;
        std::istringstream ( str ) >> res;
        return res;
    }

}
#endif

用户的输入可以是这样的格式：“1 2 3 * -3 1 * 2,-1*2,-1 0”，通常用户的输入都是以各个零极点为根的多项式之积，*是各个相乘多项式之间的分隔符, 而空白和英文逗号可以作为多项式中各个系数之间的分隔符，表示的多项式就是(s²+2s+3)(-3s+1)(2s-1)(2s²-s).于是采用Boost::tokenizer将字符串进行两层分割：第一层是乘法运算符*，第二层则是空格和英文逗号。

 #include <boost/tokenizer.hpp>

std::vector<double> poly(const std::string &myString)
{
    std::vector<double> res;
    boost::char_separator<char> sep(" ,");
    boost::tokenizer<boost::char_separator<char>> tok(myString, sep);
    for (boost::tokenizer<boost::char_separator<char>>::iterator beg =
             tok.begin();
         beg != tok.end(); ++beg) {
        res.push_back(std::stod(*beg));
    }

    std::reverse(res.begin(), res.end());
    return res;
}

std::vector<double> polyFromRawText(const std::string &rawText)
{
    std::vector<double> res = {1};
    boost::char_separator<char> sep("*");
    boost::tokenizer<boost::char_separator<char>> tok(rawText, sep);
    for (boost::tokenizer<boost::char_separator<char>>::iterator beg =
             tok.begin();
         beg != tok.end(); ++beg) {
        auto vec = poly(*beg);
        res = convolution(res, vec);
    }

    return res;
}

这段代码的作用是将用户输入分割，并且返回成一个多项式。在这里我自己实现了一个多项式的std::vector用来表示多项式的系数，并实现乘法运算convolution，并且在线性系统的类中也有两个多项式成员：传递函数的分子和分母。

实际上使用Boost::tokenizer是一种比较简单可行的方式，也可以用Boost::splitter或者用正则表达式匹配甚至直接自己写一个简单parser都可以实现功能。

多项式的富文本输出

为了让用户直观地知道输入的格式代表的多项式，应该在QLabel中将多项式以富文本的形式输出，而且应该同时输出多项式相乘和多项式展开的形式，这里多项式输出时为了追求完美，符合平时的习惯，应该特别注意系数为0,1以及正负号的问题。具体代码太长，见GitHub仓库。

截图

其他

这个APP的创意出自我的室友，他觉得每次做完自动控制原理的题之后又要打开电脑开MATLAB去检验非常麻烦，这个APP就能够解决这样的问题
APP中绘制根轨迹的增益K是用户输入的，而且绘图时是从0到K线性地取1000个点进行计算绘制，这样的效果并不一定是最好的。在MATLAB中绘制根轨迹的增益取值算法值得借鉴
本来用的是QCustomPlot来绘制曲线的，结果这个东西在手机上的渲染效果很差，于是改成了 QtCharts，发现这个模块优点很多，而且在手机上显示的效果很好
虽然GOOGLE的NDK非常坑，不过有一个替代方案据说还是不错的：Crystax NDK，不过自从2017年就没有发布新版本了，社区也不太活跃（GitHub上的代码倒还在改）

APK下载地址（GitHub镜像） APK下载地址（百度网盘镜像）