概念

原子操作:一个函数或者动作,由一个或多个指令序列实现,

  • 对外不可见,没有其他进程可以看到其中间状态或者中断这个操作
  • 保证指令序列要么都执行,要么都不执行
  • 保证了并发进程的隔离

同步:为了完成任务而建立的多个进程,这些进程为了需要在某些位置上协调工作而等待,传递信息而产生的制约关系

  • 空闲让进:没有进程处于临界区时,可以允许一个请求进入临界区
  • 忙则等待:已有进程进入临界区时,其他试图进入临界区的进程必须等待
  • 有限等待:对要求访问临界资源的进程,保证要在有限时间内进入临界区
  • 让权等待:当进程不能进入临界区时,应该释放处理机

互斥:当一个进程在临界区访问共享资源时,其他进程不能进入临界区访问共享资源
临界区:进程将访问共享资源的一段代码

  • 一个进程在临界区运行时,另一个进程无法进入临界区

  • 一次只有一个程序在临界区

死锁:多个进程相互等待导致都不能执行
活锁:进程为像一个其他进程的变化,持续改变自己的状态,但不做有用的工作
竞争:多个进程读写一个共享变量,该变量的最终指依赖它们的相对调度
饥饿:进程已经完全具备了了执行条件,但是得不到CPU资源

进程并发面临问题

  • 忙等:没有执行有用的事情但是一直占用处理机,违背了让权等待的原则;
  • 永久阻塞:需要得到临界资源的进程永远得不到资源,违背了有限等待的原则;
  • 死锁:每个进程误以为对方进入了临界区,使自己处于阻塞
  • 互斥礼让:代表进入临界资源区的标志为不断的重置和检查,重置序列无限延伸,任何进程不能进入自己的临界区

硬件方法实现互斥和同步

中断屏蔽

  • 利用开关中断指令实现,类似于原语
  • 即先关中断,关中断后即不允许当前进程被中断,也必然不会发生进程切换,然后进入临界区,直到当前进程访问完临界区,再执行开中断指令,才有可能有别的进程上处理机访问临界区。
  • 简单高效,但是不适合多处理机,只适用于操作系统内核进程,不适合用户进程

TestAndSet,Swap(TS指令/TSL指令/Swap指令)

  • TSL指令是用硬件实现的,执行的过程不允许被中断,只能一气呵成。相比软件实现方法,TSL 指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。
  • 实现简单,无需像软件实现方法那样严格检查是否会有逻辑漏洞
  • 适用于多处理机环境
  • 不满足“让权等待”原则,暂时无法进入临界区的进程会占用CPU并循环执行TSL指令,从而导致“忙等”

整形信号量

将可用的资源数定义为一个整型量$S$,初始化后可通过两个原子操作访问

  • wait(S):P操作,while(S<=0);S—-;
  • signal(S):V操作,`S++
    整形信号量不遵循让权等待原则;

记录型信号量

由两部分构成:

  • 代表资源数目的整型变量Value
  • 表示所有等待进程的进程链表L
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef struct Semaphore {
int Value;
List_of_Process L;
};
void Wait(Semaphore s){
s.Value --;
if(s.Value < 0){
L.push(now_process);
block(now_process);
}
}
void Signal(Semaphore s){
s.Value ++;
if(s.Value <= 0 ) {
next_process = L.top();
wakeup(next_process);
}
}

Value初值为1,表示只允许一个进程访问临界资源,转化为互斥信号量(二元信号量);

简单说明互斥锁和二元信号量的区别:

  • 为互斥量加锁和解锁的进程只能是同一进程;
  • 可能有某个进程对二元信号量加锁,另一个进程为其解锁;

一般来说,对于多个进程互斥访问临界资源的情况,每个进程应该都要设计代表访问临界资源的锁;

1
2
3
4
5
6
7
8
9
10
Semaphore mutex(1);
void Process1{
// 申请访问其他资源

P(mutex); // 申请进入临界区
// Critical Section 临界区代码
V(mutex); // 释放临界区资源

// 释放已申请的其余资源
}

进一步还可以利用信号量设计进程间的前趋关系;

AND信号量

将进程在整个运行过程中需要的所有资源,一次性全部地分配给进程,待进程使用完后再一起释放。只要尚有一个资源未能分配给进程,其它所有可能为之分配的资源,也不分配给他。
对临界资源的分配采用原子操作的方式;

信号量集

对每一类资源,设定一个下限值$t$和需求单位值$d$;

1
2
3
4
5
Swait(S1, t1, d1, …, Sn, tn, dn)
if ( S1≥t1 and … and Sn≥tn )
for ( i=1;i<=n; i++)
Si =Si-di;
else
  • Swait(S, d, d) 此时在信号量集中只有一个信号量$S$, 但允许它每次申请d个资源,当现有资源数少于d时,不予分配;
  • Swait(S, 1, 1) 此时的信号量集已退化为一般的记录型信号量($S>1$时)或互斥信号量($S=1$时);
  • Swait(S, 1, 0)这是一种很特殊且很有用的信号量 操作。当$S≥1$时,允许多个进程进入某特定区;当$S$变为0后, 将阻止任何进程进入特定区。换言之,它相当于一个可控开关。

管程Monitor

管程是由一个或多个过程,一个初始化序列和局部数据组成的软件模块

  • 局部变量数据只能被管程的过程访问,外部过程无法访问
  • 一个进程通过调用管程的一个过程进入管程,设计一个入口,进入管程之前先进入管程的待进入队列中;
  • 只能有一个进程在管程中执行,其他调用管程的进程将被阻塞;

image-20241026152806438

管程通过条件变量支持同步,其原子操作和普通的信号量不同;

  • cwait(c): 调用进程的执行 在条件c阻塞,管程可以被另一个进程使用;
  • csignal(c):恢复在cwait(c)之后因为某些条件被阻塞的进程;

在一个进程在管程中时,因为某种原因,这个进程发送cwait(x)将自己暂时阻塞在条件x上,此时加入条件x的条件队列,之后这个进程等待条件x的改变,以重新进入管程的待进入队列中,若进程发现条件x真的发生了改变,则发送csignal(x)通知相应的条件队列条件已经改变;

Producer-Consumer Problem

描述

  • 有一个或多个生产者生产某种资源,放入缓冲池
  • 有一个消费者从缓冲池读取资源,每次读取一项
  • 任何时候仅有一个生产者/消费者可以访问缓冲池,
  • 缓冲池已满时,生产者不再往其中添加资源;
  • 缓冲池为空时,消费者不会从中移走资源;

信号量实现

  • 利用互斥信号量mutex实现对缓冲池的互斥使用
  • 利用信号量empty full表示缓冲池中空区和满区的数量;

image-20241026162308732

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
size_t n;
Semaphore mutex(1);
Semaphore full(0), empty(n);
Item Buffer[n];
int in=0;
int out=0;

void append(Item v){
Buffer[in] = v;
in = (in+1)%n;
}
Item take(){
v = Buffer[out];
out = (out+1)%n;
return v;
}

void Producer(){
while(true) {
v = produce();

P(empty);
P(mutex);
append(v);
V(mutex);
V(empty);
}
}
void Consumer(){
while(true){
P(full);
P(mutex);
v = take();
V(mutex);
V(full);

comsume(v);
}
}

对于一系列P操作和V操作,也可以用AND信号量实现,不过注意,对P操作的顺序不能颠倒,否则将可能导致死锁;

Reader-Writer Problem

描述

  • 多个进程对同一个文件进行读写
  • 不能同时写文件
  • 不能同时读和写文件
  • 可以同时读文件

信号量实现

  • 设置写锁Wmutex,由于最多有一个进程在写,因此这应该是一个互斥信号量
  • 设置读锁Rmutex,用于记录目前在读文件的进程数ReaderCnt,这些进程应该互斥地修改它;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
Semaphore Rmutex(1)
Semaphore Wmutex(1);
int ReaderCnt = 0;

void Reader(file) {
P(Rmutex);
if(ReaderCnt == 0) P(Wmutex);
ReaderCnt ++;
V(Rmutex);

open(file);
read(file);
close(file);

P(Rmutex);
ReaderCnt --;
if(ReaderCnt == 0) V(Wmutex);
V(Rmutex);
}

void Writer(file) {
P(Wmutex);

open(file);
write(file);
close(file);

V(Wmutex);
}

死锁

哲学家进餐问题

  • 5个哲学家坐在圆桌,他们中间穿插5只筷子
  • 哲学家进餐必须同时具备左边和右边的筷子
  • 一只筷子在同一时刻只能由一位哲学家使用,
  • 哲学家在进餐完毕后必须将筷子放回原处,然后思考哲学问题;

一般我们将5只筷子设置为5个信号量,哲学家进餐前默认先拿起左边的筷子,再拿起右边的筷子后,进餐,完毕后先放下右手的筷子,再放下左手的筷子,然后思考或等待下一次进餐;

注意:

假如五位哲学家同时饥饿而都拿起的左边的筷子,就会使代表筷子的5个信号量同时置0,这时他们试图拿起右边的筷子时,都因为相互等待二陷入死锁;

可以进行如下的改进策略:

  • 限制并发量:至多允许4个哲学家同时进餐
  • 解除环路等待:指定一位哲学家必须先拿起右边的筷子
  • 恢复策略:死锁发生时,指定一位哲学家放下自己的筷子;
  • 检测策略:哲学家进餐前,同时申请两只筷子;
  • 管程优化:每次只有一个进程进入管程

产生原因

  • 竞争资源:资源包括可剥夺资源和非剥夺性资源,一般是竞争非剥夺性资源,竞争临时性资源引起;
  • 进程间推进顺序不当;

充分必要条件

  1. 互斥条件:至少有一个资源是非剥夺性的
  2. 请求并保持条件:进程因请求新的资源而保持对已有资源的占有
  3. 不可剥夺条件:已获得的资源在未使用完之前,不能被其他进程抢占
  4. 环路等待条件:存在一组进程,使得每个进程都在等待其他进程所持有的资源

注意,前三者是死锁发生的必要条件,而非充分的;

预防死锁

预防死锁发生的可能(一般不会禁止互斥条件,如果操作系统实现了互斥的话)

  • 预防请求并保持条件
    • 进程在执行前,一次申请完执行过程中可能用到的所有资源;
  • 预防不可剥夺条件
    • 进程已占用一些资源,但后续资源得不到满足,必须释放已经占用的资源;
    • 高优先级进程申请被低优先级进程占用的资源,系统将后者资源抢占,分配给前者;
  • 预防环路等待条件
    • 将资源进行排序(定义资源的线性顺序),若进程获得资源$R_i$,后续资源序号只能都大于或都小于$i$;

注意,预防死锁可能会导致资源的低效使用和低效的进程执行

避免死锁

死锁避免允许三个必要条件的发生,但是明智的选择确保不会到达死锁点,因此允许了更多的进程并发;

安全状态
系统能找到进程的执行序列,为每个进程分配所需资源,直到每个进程的最大需求 ,使得每个进程都可以顺利完成

  • 允许进程动态地申请资源
  • 分配之前检查会不会导致系统进入不安全的状态

考虑一个有$n$个进程,$m$个不同类型资源的系统,定义

1
2
3
4
5
6
struct state {
int resource[m]; // 系统中每种资源的总量,向量R
int avalaible[m]; // 未分配给进程的每种资源的总量,向量V
int claim[n][m]; // 进程i对资源j的最大需求,矩阵C
int allocation[n][m]; // 系统为进程i分配资源j的数量,矩阵A
}

不难看出以下关系成立:

  • 对于每类资源,要么可用,要么已被分配:$\forall j,R_j=V_j+\sum_{i=1}^n A_{ij}$
  • 任何进程对任何资源的请求不能超过这个系统中的资源总量:$C_{ij}\le R_i$
  • 任何进程得到的资源数不会超过最开始声明得到此资源的最大数量:$A_{ij}\le C_{ij}$
  • 启动新进程$P_{n+1}$的充分必要条件:$\forall j,R_j\ge C_{(n+1)j}+\sum_{i=1}^n C_{ij}$

安全性检查算法

系统如果要将资源分配给进程$i$,必须满足:
$$
\forall j, C_{ij}-A_{ij}\le V_j
$$
那么只需要以此找到满足上述约束关系的进程,执行完成后释放,找到下一个满足的进程;

安全性检查算法描述如下:

  1. 设置工作向量work[m]:表示系统可提供给进程继续运行所需的各类资源的数目; finish[n]:表示系统是否有足够的资源分配给进程,使之运行完成;

  2. 初始化work := available finish := false

  3. 从满足finish[i]=false的进程集合找到满足上述约束条件的进程i

    • 若能找到,执行4
    • 若不能找到,执行5
  4. 进程i得到资源执行后,释放其资源,应该执行

    1
    2
    work[j] += allocation[i][j]
    finish[j] = true

    后,返回2

  5. 若所有进程的finish值均为true,则说明系统安全,否则系统处于不安全状态;

银行家算法

某一时刻收到进程i的对系统资源的请求向量request_i

按照以下步骤对系统资源状态进行检查:

  1. 检查request_i[j]<=claim[i][j]-allocation[i][j]

    • 真,则进行2;
    • 否则认为系统出错,资源数不满足其先决条件;
  2. 检查request_i[j]<=available[j]

    • 真,则进行3;
    • 否则认为尚无足够的资源,进程i必须等待;
  3. 系统尝试为进程i分配资源,状态修改如下:

    1
    2
    available[j] -= request_i[j];
    allocation[i][j] += request_i[j];
  4. 系统执行安全性检查算法

    • 若通过检查,则正式分配资源给进程i
    • 否则恢复原来的资源状态,宣布让进程i等待;

检测和解除死锁

额外定义请求矩阵Q[n][m],表示进程i请求资源j的数量;

维护一个标记表L,最初所有进程都是未标记的;

检测死锁按照以下步骤进行:

  1. 标记allocation矩阵中一行全为0的进程;
  2. 初始化临时向量w := available
  3. 尝试查找下标i,使进程i当前未被标记,且其请求小于w;
    • 若查找失败,终止算法
  4. 进程i加入标记表L,更新w[k] += allocation[i][k]
  5. 当且仅当算法结束时存在未被标记的进程时,意味着死锁存在于这些进程之中

解除死锁的思路比较简单,以下是常见的设计:

  • 撤销所有死锁的进程:这是操作系统最常用的办法;
  • 死锁进程回滚到某些检查点,重新启动
  • 连续撤销死锁进程直到死锁不存在
  • 连续抢占资源直到不存在死锁

进程间通信

对于PV操作可以用于进程的同步和互斥,属于低级进程通信,对网络进程通信和数据交换量较大的单机进程通信不适用;
进程间通信可以利用共享存储器/消息传递/管道实现;

共享存储器

  • 基于共享数据结构的通信方式:公用某一个数据结实现信息交换
  • 基于共享存储器的通信方式:划分一块存储空间作为公用

消息传递

  • 直接消息传递:多个进程利用系统调用相互发送消息;
    • 利用send,receive原语
    • 可能产生安全问题:消息丢失,对象假冒,消息篡改
    • 一般通信有三种情况:阻塞send+阻塞receiver,无阻塞send+阻塞receiver,无阻塞send+无阻塞receiver
  • 简介消息传递:不直接发送消息给接收者,而是发到某个共享空间
    • 接受者和发送者的关系不确定:一对一,多对多,一对多,多对一
    • 需要解决共享空间的所有权问题

管道

在UNIX中,一般采用半双工的方式工作;
利用pipe函数创建管道

1
2
# include <unistd.h>
int pipe(int fd[2]);

fd[1]的输出fd[0]的输入;创建成功返回0,失败返回-1;

进程调度

如果存在多个进程竞争CPU,那么需要选择下一个要运行的进程;

  • 调度程序
  • 调度算法

目标:满足系统目标(响应时间,吞吐量,处理器效率)的方式,将进程分配称一个或多个处理器上执行;
调度层次类型:长程/中程/短程……

长程调度

决定外存上后备队列中哪个作业进入内存处理
考虑两个问题:

  1. 何时创建进程
    • 取决于多道程序的并发度;
    • 处理器的空闲时间超过某个阈值,也可能启动长程调度;
  2. 选择哪些作业进行调度
    • 取决于调度算法

中程调度

属于对换功能的一部分,用以提高内存的利用率和系统的吞吐量;

  • 内存紧张时,选择一个进程换出到外存
  • 内存充裕时,从外存选择一个挂起的进程调度到内存
  • 只有支持进程挂起的操作系统支持中程调度

短程调度

决定就绪队列中哪个进程应该获得处理器;

  • 运行频率最高;
  • 现代操作系统几乎都设计了短程调度功能;
  • 引发原因:时钟中断,io中断,操作系统调度,信号;

调度规则

周转时间

构成:作业提交给系统,到作业完成的时间间隔

  • 驻外存等待调度时间
  • 驻内存等待调度时间
  • 执行时间
  • 阻塞时间

平均周转时间
$$
T=\frac1 n \sum_{i=1}^n T_i
$$
带权周转时间
$$
W_i=\frac {T_i}{T_{service}}
$$
平均带权周转时间
$$
T=\frac1 n \sum_{i=1}^n W_i
$$

响应时间

从用户提交请求开始, 到系统首次产生响应的时间;

  • 输入传送时间
  • 处理时间
  • 响应传送时间

截止时间

  • 某任务必须开始执行的最迟时间;
  • 必须完成的最迟时间;

系统吞吐量

在单位时间内系统完成的作业数;

需求

  • 面向用户
    1. 响应时间快:使绝大多数用户的请求能在能够接受响应的时间完成,常用于评价分时系统
    2. 平均周转时间短:常用语评价批处理系统
    3. 截止时间:常用语评价实时系统
  • 面向系统:
    1. 系统吞吐量大:评价批处理系统
    2. 处理器利用率高:评价大型用户系统
    3. 公平性
    4. 资源平衡使用
    5. 优先权高进程优先调度

决策模式

  • 抢占(剥夺)方式:中断当前进程,让优先级较高的进程执行
  • 非抢占(非剥夺)方式:执行进程只有在执行完毕时才会释放处理机的进程,不适合即时性较高的场景

调度算法

系统的资源 分配策略 规定的资源分配算法,以针对不同的系统目标;
常见的调度算法:

  • 先来先服务
  • 时间片轮转
  • 短作业优先
  • 剩余时间最短
  • 最高响应比优先
  • 反馈

先来先服务FCFS

选择最先进入就绪队列的进程投入执行,进程按照请求CPU的顺序使用CPU
评价:

  • 属于非抢占调度方式
  • 有利于CPU繁忙的进程,不利于IO繁忙的进程
  • 不利于直接用于分时系统
  • 平均周转时间长
  • 对于长进程有利,不利于短进程
  • 简单,但是相对公平

时间片轮转RR

CPU被每个进程分配自己的时间片,在时间片结束时进程还在运行,则抢占其CPU分配个下一个进程;
被剥夺CPU的进程插入到队列末尾等待下一次的调度;
如果该进程在时间片内注射或结束,则立即切换CPU;
评价:

  • 属于抢占式调度
  • 常用语分时系统和事务处理系统
  • 时间片设置和系统性能,响应时间密切相关(时间片短导致调度程序和中断次数多,时间片长引起短交互请求的响应时间变长)
  • 时间片的大小的确定要考虑最大最大用户数量,响应时间,系统效率

虚拟轮转法VRR

增加一个基于FCFS的辅助队列,接受I/O阻塞完成的进程,调度优先于主就绪队列,但是占用处理机时间小于主就绪队列的时间片
评价:

  • VRR相较RR公平
  • 常用语分时系统,事务处理系统

短进程优先SPN/SJN

进程的执行时间预知,选择短进程优先调度
评价:

  • SPN属于非抢占式调度算法
  • 对长作业不利,可能导致饥饿
  • 有利于短进程,减小了平均周转时间
  • 缺少剥夺机制,不适用分时系统或事务
  • 算法不一定准确,不一定真正做到短作业优先

剩余时间最短者优先SRT

调度程序总是选择预期时间最短的进程
当新进程加入就绪队列,若它比当前运行进程更短的剩余时间,就会发生抢占
在SPN上增加了剥夺机制;
评价:

  • 不像FCFS偏爱长进程,也不像RR产生额外的中断,减小了开销
  • 在周转时间方面,SRT性能比SPN更好,短作业可以立即被选择执行
  • 需要预估服务时间,可能存在进程饥饿,必须记录进程的已服务时间

最高响应比优先HRRN

当前进程执行完毕/需要阻塞时,选择就绪队列中响应比最该的进程投入执行;
$$
R_p=\frac{T_{wait}+T_{service}}{T_{service}}
$$
评价:

  • HRRN本质上是动态优先权调度算法
  • 结合了FCFS和SPN,既照顾了短进程,又考虑了到达的先后次序,不会使长进程长期得不到服务
  • 每次调度前需要计算响应比,既增大了开销又难以准确计算

反馈调度法FB

采用多级队列区别对待,惩罚长进程;

  • 准备多个独立的,优先级不同的就绪队列
  • 优先级高的队列被优先调度
  • 进程执行过程可能 被降级,整个生命周期内可能位于不同的队列;

以基于时间片轮转的FB算法为例:

  • 设置多个就绪队列,其优先级不同
    • 优先级约到的队列,进程执行的时间片越小
  • 新进程进入,首先放入第一个队列的队尾,FCFS原则排队
  • 若进程在规定时间片完成,则退出
    • 队列$i$调度的进程允许执行$2^i$的时间,才会被抢占
    • 若时间片完则被抢占被抢占的进程降级到下一个优先队列
  • 到末尾队列不再降级
  • 当且仅当上一个队列空闲,下一个队列的进程才被调度

评价:

  • FB算法具有较好的性能,平衡了各类需求
  • 有利于终端作业用户,这类通常为短作业,一般能在第一队列规定的时间片做完
  • 对于长批处理作业,也能在前几个队列规定时间片完,但是不断有长进程到来时,可能存在饥饿

实时系统和实时调度

实时系统

系统能及时响应外部事件的请求,规定时间内完成对该事件的处理,控制所有的实时任务协调运行
实时操作系统的特点

  • 可确定性:任务按照固定的预先确定的时间间隔进行
  • 可响应性:关注系统知道中断后为中断提供服务时间
  • 用户控制:用户能区分软实时和硬实时任务,控制任务优先级
  • 可靠性:实时控制,响应事件,保障性能
  • 失效弱化:不能满足所有任务的实时性时,优先满足重要的,优先级高的任务期限,减少系统故障
    调度方式
  • 基于时间片的轮转抢占式
    • 进程按照时间片轮转方式执行,到达进程放在就绪队列末尾
    • 时间片完进行调度,响应时间为秒级,广泛用于分时系统和一般实时处理系统
  • 基于优先级的非抢占式
    • 进程按照优先级,非抢占的方式,新来的进程在就绪队列的头部
    • 当前进程阻塞或完成时,立即调度新来的进程
    • 响应时间为数百毫秒到数秒,用于多道批处理系统和不太严格的实时系统
  • 基于优先级的抢占点抢占调度
    • 进程按照优先级,抢占方式执行
    • 下一个剥夺点到来时,立即占用CPU
    • 响应时间为数十毫秒,用于一般实时系统
  • 立即抢占式调度
    • 按照优先级,抢占方式
    • 响应时间在微妙级,用于苛刻的实时系统

实时任务

具有及时性,常常被重复执行,往往预先设定的特定进程,在实时系统中称为任务

  • 开始截止时间:该时间之前任务必须执行
  • 完成截止时间:该时间之前任务必须结束
    分类:
  • 按截止时间划分:硬实时任务,软实时任务
  • 按周期性划分:周期性实时任务,非周期性实时任务

实时调度

静态表驱动调度

用于调度周期性实时任务
按照任务周期到达的时间,执行时间,完成截止时间以及任务的优先级,制定调度表,调度实时任务
比如:最早截止时间优先(EDF)调度算法
任何任务调度申请改动都会引起调度表的修改,带来不灵活性;

静态优先级抢占调度

多用于非实时多道程序系统
优先级确定方法很多
实时系统一般对任务的限定时间赋予优先级;
比如:速度单调算法(RMS)为实时任务赋予静态优先级

  • 任务速率:任务周期以赫兹为单位
  • 优先级确定:任务周期越短,优先级越高;优先级函数时任务速度的单调递增的函数
  • 系统按任务优先级的高低工作进行调度;

基于动态规划的调度

实时任务到达以后,系统为新到达的任务和正在执行的任务动态创建调度表
在当前执行进程不会错过截止时间的条件下,如果也能使新到达任务在截止时间完成下,则立即调度执行新任务;

动态尽力调度法

广泛用于非周期性实时任务调度
当任务到达时,系统根据属性赋予优先级,优先级高的先调度;
比如EDF算法总是尽力尽早调度紧迫任务;
缺点:当任务完成或者截止时间到达时,很难知道该任务是否满足其约束时间;

限期调度

对具有完成期限的周期性实时任务

这类任务往往周期性可预测的
一般采用最早截止时间优先调度算法EDF;

对具有开始期限的非周期性实时任务

这类任务往往是非周期的不可预测的
预先知道任务的截止时间可采用允许CPU空闲的EDF调度算法;

  • 优先调度截止时间最早的合格任务,并运行完毕
  • 合格任务可以是还未就绪,但是事先知道开始截止时间的任务
  • CPU利用率不高,但是系统的任务都能按要求完成

实时系统处理能力限制

假定系统中有$m_i$个周期性硬实时任务,处理时间分别为$c_i$,周期为$p_i$,则在单处理机的情况下,满足如下限制
$$\sum_{i=1}^m \frac{c_i}{p_i} \le 1$$
CPU利用率=任务执行时间/任务周期;
各个任务的处理器利用率总和不超过1;

优先级反转

一个高优先级任务简介被一个低优先级任务所抢占,使得两个任务的相对优先级被倒置;
系统不希望这种调度任务状态,但是可发生于任何基于优先级的可抢占的调度方案;
解决方案:优先级继承,优先级较低的任务继承任何与其共享同一资源的优先级较高的任务的优先级

进程

什么是进程

程序的顺序执行与并发执行

顺序执行:若干程序和程序段必须严格按照某种先后顺序执行

  • 顺序性:操作严格按照程序规定的顺序执行;
  • 封闭性:程序运行时占用全机资源;
  • 可再现性:只要程序的执行环境和初始资源的条件相同,结果就相同;

并发执行:多个时间在同一个时间间隔内发生;

  • 应用级并发:事务处理系统,数据库管理系统
  • 系统级并发:操作系统;
  • 间断性:由于资源的共享和相互合作,程序体现执行-暂停-执行的现象
  • 失去封闭性:程序在并发执行时,是多个程序共享系统的资源,资源的状态有多个程序来改变;
  • 不可再现性:程序在并发执行时,由于失去了封闭性,多次重复可以得到不同的结果;

image-20240927150453849

进程

引入进程的目的:为了 控制 多道程序能够 正确的并发 执行

定义:(程序代码program code + 数据集set of data + 进程控制块PCB,process control block)

  1. 一个正在执行的程序;
  2. 一个正在计算机上执行的程序实例;
  3. 一个能够被调度到处理器上执行的实体;
  4. 由一串指令的执行、当前状态和一组正在使用的系统资源表征的活动单元;

进程的物理存在:进程映像

  • Process Image=PCB+program+data+stack
  • 进程映像取决于文件格式;

系统中同时存在的诸进程相互独立,也相互关联,这取决于设计模式;

可以说,并发基于进程;

进程控制块

进程执行的任意时刻可以由 进程控制块 表征,组成如下:

  1. 标识符
  2. 状态
  3. 优先级
  4. 程序计数器
  5. 内存指针
  6. I/O状态信息
  7. 记账信息……

注意,PCB常驻内存,PCB是进程存在的唯一标志

进程的特征

  • 动态性最基本特征,是计算机的执行的程序实例,存在生命周期;
  • 并发性:多个进程实体存在于内存中也能在一段时间内同时运行,可以说进程的设计就是为了操作系统的并发;
  • 独立性:进程实体是独立运行的基本单位,也是系统独立获得资源和调度的基本单位,各个进程的地址空间相互独立除非进程间相互通信;
  • 异步性:各个进程按照独立的,不可预知的速度向前推进;

注意:进程和程序之间不存在一一对应的关系;

进程带来的挑战

  • 空间开销:为进程建立数据结构PCB
  • 时间开销:管理和协调,跟踪,填写和更新相关的数据结构,切换进程,保护现场
  • 控制复杂性:协调多个进程对资源的竞争和共享,预防解决多个进程因为资源竞争问题带来的故障

进程状态模型

由于进程具有动态性,执行间断性和多种状态的特征,需要建立进程状态的自动机描述;

进程轨迹trace :进程执行的指令序列,描述单个进程的行为;

调度器dispatcher:调度多个进程的执行;

以下是 轮转(round-robin) 的例子:通过指定一个时间片,处理器决定是否切换进程;

image-20240927152122797

image-20240927152140953

两状态模型

进程处于两种状态之一:

  1. 运行态:进程队列的头部进程被系统调度执行;
  2. 非运行态:进程创建后,以非运行态进入进程队列中;

进程队列:存放指向特定进程的指针;

image-20240927152317809

三状态模型

进程处于三种基本状态之一:

  1. 就绪ready:
    • 进程已经获得除开CPU外的所有必要资源后,只需获得CPU立即执行进程
  2. 执行running:
    • 进程获得CPU,程序正在执行;
  3. 阻塞waiting:
    • 正在执行的进程因为其他事件的等待无法继续执行;
    • 进程放弃处理机而处于暂停状态;

对于一些嵌入式的操作系统,三状态模型足以描述:

image-20240927153655741

注意:

  • 状态转换并非都可逆
  • 一个进程在任何一个指定的时刻必须而且只能处于一
    种状态
  • 时间片完也不是执行-就绪的唯一原因,可能是高优先级抢占控制权
  • 在单处理机系统中,只有一个进程处于执行状态

五状态自动机

进程新增两个状态后真正称为自动机模型:

  • 新建New:
    • 进程刚刚创建,OS完成了进程创建的必要工作(构造了进程标识符,创建了进程管理的表格)
    • OS未将进程加入可执行进程组,进程自身未进入主存,进程尚未被同意执行,进程的程序也没有分配空间而保存在辅存;
    • 进程创建原因:新的批处理作业,交互登陆,提供服务,现有进程派生
  • 终止Exit
    • 进程不再具有执行资格;
    • 表格和其他信息暂时保留,OS从可执行进程组释放;
    • 原因:正常完成,超时,无可用内存,各种错误…

image-20240927155128295

注意:

  • 加载/接纳:OS做好接纳进程的准备后,将一个进程从新建态转换成就绪态;
  • 就绪-退出,阻塞-退出:某些系统中,父进程可以在任何时候终止一个子进程,这样的转换可能存在;
排队模型实现:维护就绪队列和阻塞队列
  • 进入OS的每个进程放在就绪队列中,OS选择进程运行时在就绪队列中选择一个;
  • 运行的程序被移除处理器后,要么终止,要么进入就绪队列或阻塞队列
  • 某事件发生导致阻塞队列中的相应进程进入就绪队列中;

具体实现:

多阻塞队列可以避免对很长的队列进行扫描;

image-20240927160858477

七状态自动机

交换技术swapping和挂起suspend

进程竞争内存资源:内存紧张,或者所有进程因为某事件等待,但是无就绪进程,处理机实际空闲

解决方案:扩充内存,swapping

  • 将内存中处于阻塞、就绪、甚至是执行状态的进程swapping-out进外存(磁盘)
  • 不再参与CPU的竞争,我们把这种静止状态称为挂起状态;
  • 在磁盘中维护一个挂起队列,建立虚存;
  • 当存在已具备运行条件的进程或进程所需要的数据和程序,Swapping-in到内存。

进程挂起的原因:

  • 进程全部阻塞,处理机空闲
  • 交换,如系统负荷过重,内存空间紧张
  • 操作系统的需要,操作系统可能需要挂起后台进程或一些服务进程,或某些可能导致系统故障的进程。
  • 终端用户的请求,如调试
  • 父进程请求

被挂起进程的特征

  • 不能立即执行
  • 挂起条件独立于阻塞条件
  • 使之挂起的进程:自身、OS、父进程
  • 激活挂起进程的进程:实施挂起操作的进程

当被挂起的进程返回内存时,OS不一定执行的准备,进一步划分:

  • 就绪挂起:进程在外存,只要调入内存并获得CPU即可执行
  • 阻塞挂起:进程在外存,并等待某事件

image-20240927162304899

注意:

  • 加载:新建进程后,进程要么加入就绪队列,要么进入就绪挂起队列,视当时的资源而定;
    • 创建进程的just-in-time原理:尽可能推迟创建进程以减小系统的开销;
  • 运行-就绪挂起:一般来说,运行进程的分配时间到期后就会转换成就绪态,但是某个具有高优先级的进程位于阻塞/挂起队列不被阻塞时,OS会抢占这个进程

进程描述

进程的执行必须由操作系统分配资源,操作系统是资源的管理者:采用表格记载资源的信息,进而实现资源的管理,维护和更新;

  • 内存表
  • I/O表
  • 文件表
  • 进程表

image-20240927163242526

进程控制块

包括信息主要有三类:

  • 进程标识信息;唯一标识一个进程
    • 内部标识符:操作系统为每个进程赋予的一个唯一整数,便于系统控制
    • 父进程标识符
    • 用户标识符
  • 处理机状态信息:主要是上下文,由处理器的各种寄存器中的内容组成的
    • 通用寄存器
    • 控制和状态寄存器
    • 栈指针
  • 进程控制信息:与进程调度和进程切换有关的信息
    • 进程状态
    • 进程优先级
    • 时间记账
    • 阻塞原因
    • 链接指针
    • 进程间通信
    • 程序和数据地址
    • 资源所有权和使用情况

进程的组织方式

索引

系统为所有进程的状态建立几张索引表;

image-20240927164502164

链接
  • 单一队列:所有PCB块连接成一个队列

    image-20240927164522935

  • 多级队列:相同状态的PCB块连接成一个队列

    image-20240927164547710

内核

内核是操作系统的核心,是包含重要系统功能的部分,常住内存以提高操作系统的系统功能;

不同操作系统对内核的设计(功能范围的设定)不同;

  • 资源管理

    • 进程管理:进程的创建和终止,调度,分配,切换,同步和进程间通信,管理PCB

    • 存储管理:为进程分配地址空间,交换,页和段管理

    • I/O管理:缓冲区管理,为进程分配I/O通道

  • 支撑功能

    • 中断:操作系统的一切重要活动最终依赖于中断
    • 时钟
    • 记账

执行模式

  • 大多数处理器至少支持两种模式:内核模式,用户模式
  • 某些指令只能在特权模式运行,部分内存只能在特权模式下访问
  • 采用两种模式可以保护操作系统和重要的系统操作表不受程序干扰
  • 查看运行模式:程序状态字寄存器PSWR下指示执行模式的位

模式切换:

  • 原因:系统调用或中断,中断发生时,将程序计数器设置为中断程序处理的开始地址,切换成内核模式使得中断程序可以执行某些特权指令
  • 中断不一定引发进程切换,也不一定造成模式切换,模式切换和进程切换无决定关系

进程控制

进程控制包括以下事件:

  • 进程的穿件与撤销
  • 进程的阻塞和唤醒
  • 挂起和激活
  • 进程切换

实现方式:原语Primitive

  • 原语用于完成一定功能的过程,定义了原子操作
  • 其执行过程不允许被中断;

create原语:创建进程

  • 为新进程分配唯一一个进程标识符
  • 为进程分配空间
  • 初始化进程控制块(标识信息,处理机状态信息,调度信息)
  • 建立连接,插入就绪(就绪/挂起)队列
  • 建立扩充其他相关的数据结构

后面两步是方便操作系统管理进程的必要步骤;

进程终止原语

  • 根据标识符找到其PCB,读出进程的状态
  • 对于执行状态的进程,终止它,调度下一个进程就绪进程的执行
  • 若进程存在子进程,不同的操作系统有不同的处理方式,挂在其他结点或者终止它
  • 将进程的全部资源归还(父进程或者OS)
  • 被终止进程的PCB从队列中移除,等待其他程序搜集信息

进程阻塞

  • 对于执行状态的进程发生阻塞时,使用Block()原语将自己阻塞
  • 将PCB的状态由执行到阻塞将PCB加入阻塞队列
  • 将处理剂分配给下一个就绪进程并切换

进程唤醒

  • 被阻塞进程期待的事件出现时,有关进程调用唤醒原语wakeup(),等待该事件的进程唤醒
  • 唤醒进程原语执行:将被阻塞进程从队列移出,将PCB中现行状态由阻塞改为就绪,插入到就绪队列中

进程挂起

出现引起进程挂起的事件时,系统将利用挂起原语suspend()将指定挂起;

  • 检查被挂起的状态
  • 插入相应队列

进程激活

  • 发生激活进程的事件时,将在外存上处于挂起的进程换入内存
    • 利用激活原语active()将指定进程从外存调入内存:检查进程状态,插入相应队列

进程切换

进程切换:调度另一个就绪进程占用处理器
进程上下文:进程执行的现场
发生原因:

  • 时钟中断
  • IO中断
  • 内存失效
  • 陷阱
  • 系统调用

步骤:

  • 保存处理器上下文,包括程序计数器和其他寄存器
  • 更新运行进程的PCB
  • 将PCB移动到相应队列
  • 选择另一个进程执行
  • 更新另一个PCB
  • 恢复被选择的上下文

线程

线程是进程的一个实体,是独立调度和分派的基本单位;
进程是系统进行资源分配和调度的独立单位;
线程是进程的一个实体,是对调度和分配的基本单位;

  • 进程是系统中拥有资源的单位,比如进程映像的地址空间,全局变量,打开文件,IO设备
  • 线程,拥有少量的私有资源(线程控制块,栈…)
  • 同一进程哪的线程共享全部资源
  • 同一进程的线程切换不会引发进程切换
  • 不同进程中线程切换将引起进程切换
  • 同一进程的多个线程也存在并发,提高系统资源的使用和系统吞吐量
  • 线程间通信比进程间通信快很多
  • 线程的系统开销小于进程,同一进程的多个线程同步和通信更容易

状态

  • 就绪状态
  • 执行状态
  • 阻塞状态

一般不具有挂起状态,一个进程可以创建和撤销多个线程,同一个进程的多个线程可以并发执行

基本操作

  • 派生spawn:
  • 阻塞block
  • 解除阻塞ubblock
  • 结束finish

分类

  • 用户级线程
  • 内核级线程
  • 混合线程

绪论

操作系统

操作系统:控制应用程序执行的程序,是应用程序和硬件之间的接口;

本课程默认单核单CPU;

操作系统是一组控制和管理计算机硬件和软件资源,合理地对各类作业进行调度,以及方便用户使用的 **程序的集合 **;

  • 内存管理;
  • 处理机管理;
  • 作业管理;
  • I/O设备管理;
  • 文件管理;

操作系统的设计目标

  • 便利性:使计算机易于使用;
  • 有效性:允许以更有效的方式使用计算机资源;
  • 扩展能力:不妨碍服务的情况下,有效的开发测试和引进新功能;

操作系统的位置

作为用户/计算机接口

image-20240919105310309

操作系统的服务

  • 程序开发:提供一系列工具和服务(如编辑器和调试器)
  • 程序运行:为用户处理调度问题,如加载到内存、初始化I/O 设备等
  • I/O 设备访问:提供统一接口,隐藏具体的 I/O 操作指令
  • 文件访问控制:屏蔽存储介质细节
  • 系统访问:提供接口,防止未授权访问行为
  • 错误检测和响应:软、硬件错误
  • 日志:收集资源的利用率信息、监控性能特性

操作系统:资源管理者

  • 资源管理者:控制数据的移动,存储和管理;
  • 控制机制的特殊性:os同为一种程序,但是会转交控制权,必须依赖处理器才能恢复控制;

操作系统的发展过程

硬件升级+新设备出现+错误修复

串行处理

  • 无操作系统;
  • 操控控制台(显示灯,触发器,输入设备,打印机…)运行程序;
  • 程序通过输入设备载入计算机;
  • 用户按顺序访问计算机;
  • 调度慢,启动时间长;

简单批处理

  • 采用监控程序:对一批作业自动处理,内存中只能存在一道作业,作业自动续接,内存保护,定时器防止作业独占系统,拥有特权指令,允许中断;
  • 处理器常处于空闲状态(I/O设备速度比处理器慢许多);
  • 拥有内核模式和用户模式

多批道处理系统

  • 内存存放多个作业;
  • 多个作业并发运行(并发:在某一时间切片内有多个作业运行,但某一时刻只有一个作业),可以显著提高系统资源的利用率;
  • 作业调度系统负责作业的调度;
  • 硬件支持:I/O中断,直接存储器访问;
  • 多道性,调度性,无序性,无交互能力;

分时系统

  • 采用多道程序处理多个作业,多个用户共享处理器,多个用户通过不同的终端同时访问系统;
  • 多路性,独立性,及时性,交互性;

实时系统

系统能够(及时 即时 )响应外部事件请求 在规定的时间内完成对该事件的处理,并控制所有实时任务协调一致地运行。

  • 软实时系统:各个任务运行得越快越好,并不要求限定某一任务必须在多长时间内完成。
  • 硬实时系统:各任务不仅要执行无误而且要做到准时。
  • 实时性、可靠性、多路性、独立性、交互性;

操作系统的主要功能

进程

进程:一个正在 执行 的程序,计算机中正在 运行 的程序的一个实例,可分配给处理器并由处理器 执行 的一个实体;

  • 一段可执行的程序
  • 程序所需要的相关数据(变量、工作空间、缓冲区等)
  • 程序的执行上下文(进程状态):操作系统用来 管理和控制进程所需的所有数据

设计协调不同活动的系统软件非常困难,为了解决上述问题,需要一种系统级的方法来监控和控制处理器上各种程序的执行;

以下是可能出现的问题:

  • 不正确 的同步
  • 失败的互斥
  • 不确定的程序操作
  • 死锁

下图是一种典型的进程实现方法:

image-20240919105500274

内存管理

操作系统进行存储管理的任务如下:

  • 进程隔离:每个进程拥有独立的地址空间,互不干扰;
  • 自动分配和管理:动态分配,对程序员透明;
  • 支持模块化:动态加载,销毁程序员定义的模块;
  • 保护和访问控制:一个程序的存储空间不能被其他程序任意访问;
  • 永久存储:关机后依然存储信息;

操作系统的存储管理由 文件系统虚拟内存 实现;

文件系统

文件是一个有名称的对象,是访问控制和保护的基本单元;

文件系统实现了长期存储;

虚拟内存

内存:一系列长度固定的帧组成,每个帧的大小与页面大小相同。对需要执行的程序,它的所有或部分页面必须在内存中;

磁盘:辅存(磁盘)可以容纳很多长度固定的页。用户程序由很多页组成,所有程序和操作系统的页都以文件的形式保存在磁盘上。

  • 程序以 逻辑方式 访问存储器;
  • 多作业同驻留内存;
  • 每个作业部分驻留(主要);
  • 换入,换出机制;

虚拟内存寻址如下:

image-20240919112108136

信息保护和安全

操作系统的典型安全问题:

  • 可用性:保护系统不被中断运行
  • 保密性:保证用户不能读取未授权访问的数据
  • 数据完整性:保护数据不被未授权修改
  • 可靠性:涉及用户身份的正确认证和消息或数据的合法性

调度和资源管理

操作系统的一个关键任务是管理各种可用资源(如内存空间、I/O设备和处理器等),并调度各种活动进程使用这些资源

  • 公平性:所有参与竞争某一特定资源的进程都能几乎相等且公平地访问资源
  • 有差别的响应性:区分进程类型且可动态调整
  • 有效性:最大化吞吐量(并发)和最小化响应时间,需要找到平衡点以折中处理矛盾需求

操作系统的目标和功能

  • 处理机管理

    处理机管理的主要任务是对处理机进行分配,并对其运行进行有
    效的控制和管理

    在多道程序环境下,处理机的分配和运行都是以进程为基本单位,因而对处理机的管理可归结为对进程的管理

    • 进程控制:为作业创建进程,撤销已结束的进程,以及控制进程在运行过程中的状态转换;
    • 进程同步:对诸进程的运行进行协调,包括进程互斥与进程同步
    • 进程通信:实现相互合作进程之间的信息交换,包括直接通信与间接通信;
    • 调度:按照一定的算法对作业与进程进行调度。
  • 存储器管理

    存储器管理的主要任务是为多道程序的运行提供良好的环境,方
    便用户使用存储器,提高存储器的利用率,以及从逻辑上来扩充
    内存。

    • 内存分配:为每道作业分配内存空间,使它们“各得其所”,提高存储器利用率,减少不可用的内存空间。
    • 内存保护:确保每道用户程序都在自己的内存空间中运行,互不干扰;
    • 地址映射:将地址空间中的逻辑地址转换为内存空间中对应的物理地址;
    • 内存扩充:借助虚拟技术,从逻辑上扩充内存容量;
  • 设备管理

    设备管理的主要任务,是完成用户提出的I/O请求,为用户分配
    I/O设备提高CPU和I/O设备利用率提高I/O速度以及方便用户
    使用I/O设备

    • 缓冲管理:管理好各种类型的缓冲区,以缓和CPU与I/O速度不匹配的矛盾,提高CPU和I/O设备的利用率。
    • 设备分配:为用户分配其所需的设备。
    • 设备处理又称设备驱动程序,实现CPU与设备控制器之间的通信。
  • 文件管理

    文件管理的主要任务,是完成实现文件的虚拟存取和高速存取
    方便用户访问文件、保存文件并维护其内容的完整性。

    • 文件存储空间的管理:为每个文件分配必要的外存空间,提高外存的利用率,并能有助于提高文件系统的运行速度。
    • 目录管理:为每个文件建立其目录项,并对众多的目录项加以有效的组织,以实现方便的按名存取。
    • 文件的读/写管理和保护
  • 命令接口

    为了方便用户对计算机系统的使用与编程,操作系统向用户提供
    了用户与操作系统的接口,简称用户接口

    • 命令接口:
      • 用户利用这些操作命令来组织和控制作业的执行
      • 按作业控制方式的不同,可以将命令接口分为联机命令
        接口和脱机命令接口
    • 程序接口
      • 程序接口由一组系统调用命令组成
      • 这组系统调用命令向系统提出各种服务请求,如使用各种外部设备,进行有关磁盘文件的操作,申请分配和收
        回内存以及其他各种控制要求。

操作系统的基本特征

  • 并发性

    • 在多道程序环境下,同一时刻只能有一条指令执行;
    • 但多个进程指令被快速的轮换执行,使得在宏观上具有多个进程同时执行的效果,但在微观上并不是同时执行的;
    • 可以让CPU、I/O设备并行工作,提高资源利用率;
  • 共享性

    • 系统中的资源可供内存中多个并发执行的进程共同使用
    • 临界资源:在一段时间内,只允许一个进程访问,必须互斥访问共享,比如打印机
    • 非临界资源:在一段时间内,允许多个进程访问,允许同时访问共享,比如磁盘
  • 虚拟性

    • 通过某种技术把一个物理实体变为若干个逻辑上的对应物
    • 时分复用:虚拟处理机,虚拟设备
    • 空分复用:虚拟磁盘,虚拟内存
  • 异步性

    • 多道程序环境下,程序执行过程是异步的,这意味着何时执行,执行顺序,完成运行时间都将带来不确定性
    • 不确定性不是指程序的执行结果

操作系统的体系结构

  1. 无结构
    • 存在于早期的操作系统,侧重于功能实现和效率提高;
    • 难以调试与维护,扩展性差;
  2. 模块化结构
    • 按功能划分若干个模块,模块之间通过接口交互;
    • 衡量标准:内聚性,耦合度;
    • OS设计正确性高,易于理解和维护;
    • 接口间调用关系变得复杂可能导致耦合度降低,模块之间存在复杂的依赖关系
  3. 分层式结构
    • 按功能图的调用顺序等原则划分为若干层;每层只能使用其下层提供的服务;每层对其上层隐藏其下层的存在;
    • 易于保证系统的正确性,易于维护理解和维护,易于扩充;
  4. 微内核结构
    • 机制,策略分离:基于优先级的进程调度中,选择进程,为之分配处理机,属于机制;为每个进程设置优先级属于策略;
    • 微内核基本功能:进程管理,低级存储器管理,中断和陷入处理;
    • 优点:提高了可扩展性,可靠性,可移植性,提供了分布式系统的支持;
    • 缺点:运行效率有所降低,因为消息传递机制和模式切换会带来开销

Background

在实际工程中许多函数的原函数并不容易求出,因此对它们使用Newton-Lebniz公式是相当困难的,因此衍生出数值积分,基本思想就是对于一个黎曼可积分的函数,不断细分积分区间对小面积求和得到定积分的近似值;

但是过于细致的区间划分会导致大量资源的消耗,因此这篇文章旨在介绍一种启发式的办法来使得误差控制在我们接收范围内同时减少对计算资源的消耗;

由于对数值分析的了解还不够,不少内容只能留坑了;

启发式的策略主要有以下几种:

  1. 误差估算与细分
    在自适应梯形积分中,可以利用Richardson外推或其他误差估计技术估算当前的误差。如果对某个区间的误差估计超出了预期阈值,只有这些区间会被进一步细分,从而减少不必要的计算。
  2. 局部适应性
    对于有急剧变化或高度非线性的函数,使用相同数量的区间可能会导致某些部分的误差大于其他部分。在这种情况下,可以设计算法以更高的密度对这些特定区域进行采样,同时对函数较为平缓的部分进行较少的采样。同时,也应该自适应的调整步长,在函数变化剧烈的地方采用较小的步长,而在平缓区域使用较大的步长。
  3. 多步骤递增
    不是一开始就使用非常高的划分数,可以从一个较小的区间数开始,并逐步增加,直到满足精确度要求,以此来优化计算时间。
  4. 停止准则的动态调整
    动态调整误差阈值,可以在算法运行过程中根据已经计算的结果和剩余区间来适应性地调整。

Content

梯形积分

在matlab中有一个现成的函数可供调用:
Q=trapz(x,y)表示y在x细分下的梯形积分,注意Q求出来并不是真实精确的积分结果;

梯形公式将图像线性近似$f(x)=f(a)+\frac{f(b)-f(a)}{b-a}(x-a)$,并用线下方的梯形面积替代积分面积:
$$
\int_{a}^{b}f(x)dx\approx(b-a)\frac{f(a)+f(b)}{2}
$$

其中如果将区间细化为$a=x_0<x1<…<x_{N-1}<x_N=b$,那么计算结果为
$$
\int_{a}^{b}f(x)dx=\frac{b-a}{2N}(f(x_0)+\sum_{i=0}^{N-1}f(x_i)+f(x_N))
$$

$$
R_T(f)=-\frac{(b-a)^2}{12}f’’(\xi)
$$

用matlab实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
x=linspace(0,pi,3);
y=sin(x);
my_trapz_res=my_trapz(x,y)
trapz_res=trapz(x,y)

function res=my_trapz0(f,a,b)
res=(b-a)*(f(b)+f(a))/2;
end

function res=my_trapz(x,y)
%x,y传入的应该是一对长度相等的向量
n=length(x);
res=0;
for i=2:n
res=res+(x(i)-x(i-1))*(y(i)+y(i-1))/2;
end
end

从结果上看到,和官方提供的函数并无多大区别:

1
2
3
4
5
6
7
8
my_trapz_res =

1.5708


trapz_res =

1.5708

在自适应梯形积分中,可以利用Richardson外推或其他误差估计技术估算当前的误差。如果对某个区间的误差估计超出了预期阈值,只有这些区间会被进一步细分,从而减少不必要的计算。(留坑)

自适应Simpson积分公式

在Simpson积分中,将图像近似为一个二次函数$f(x)=Ax^2+Bx+C$,那么积分可以做如下近似:
$$
\int_{a}^{b}f(x)\approx\frac{A}{3}(b^3-a^3)+\frac{B}2(b^2-a^2)+C(b-a)
$$

$$
=(b-a)[\frac{A}{3}(b^2+a^2+ab)+\frac{B}{2}(b+a)+C]=(b-a)\frac{f(a)+f(b)+4f(\frac{a+b}{2})}6
$$

我们也采用变步长的启发式策略:

  • 对于一个极小的区间认为他的Simpson值加上误差容忍可以近似为积分值;
  • 二分区间分别计算左边区间的Simpson值和右边区间的Simpson值
  • 如果两值加起来与整个区间Simpson值差距不超过15倍得误差容忍度,就认为这个区间足够小,返回这个小区间得积分值;
  • 否则需要继续递归,返回区间的左边积分值加上右边积分值;

matlab程序如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
quad(@(x)sin(x),0,pi)
my_quad(@(x) sin(x),0,pi)


function res=my_simpson(f,a,b)
res=(b-a)*(f(a)+f(b)+4*f((a+b)/2))/6;
end

function res=my_quad(f,a,b,tol)
if nargin==3
tol=10^(-6);
end
mid=(a+b)/2;
quad_all=my_simpson(f,a,b);
quad_l=my_simpson(f,a,mid);
quad_r=my_simpson(f,mid,b);
if(abs(quad_l+quad_r-quad_all)<15*tol)
res=quad_l+quad_r+(quad_l+quad_r-quad_all)/15;
else
res=my_quad(f,a,mid,tol)+my_quad(f,mid,b,tol);
end
end

可以看到和官方提供的quad函数没有太大差距:

1
2
3
4
5
6
7
8
ans =

2.0000


ans =

2.0000

洛谷模板题

请注意,自适应simpson公式数值积分适用于精度要求低,被积函数平滑性较差的数值积分;

高精度Lobatto积分法

留坑,暂时找不到资料

Remark

这里大多数数值积分的介绍都缺少一点理论知识,等哪天补一补数值计算再回来填坑了;

其中的启发式算法还是很不错的;

Backgrond

最近越来越依赖键盘了,鼠标是不想动一点,希望能汇总下自己常用的快捷键提高工作效率,不需要花时间bing;

Content

Windows Desk

win+ 一类
快捷键 效果 用途
win+R 打开终端 输入指令
win+R
Ctrl+Shift+Enter
以管理员模式打开命令行窗口 避免权限不够
win+D 快速切换回桌面壁纸 工作做完了想看看可爱的萝莉
win+L 快速锁屏 紧急避险,比如你的黄油刚好进入HCG但是你的舍友就在你的后面
win+E 打开文件资源管理器 配合方向键快速打开常用的文件夹
win+I 快速打开设置界面 比如连接WIFI,蓝牙之类的活,需要配合Tab键食用
win+V 剪切板 之前剪切的内容,还有一些emoji表情和一些逆天符号
win+方向键 自由分屏 同时看多个页面的时候比较好用
win+Tab 新建桌面 抄袭学长代码还想稍微看懂那么一点点自己写那么一点点很有用
win+Ctrl+$\gets /\to$ 左右切换桌面 配合上一个快捷键食用
win+ +/- 放大缩小桌面 近视人群专用
Ctrl+一类
快捷键 效果 用途
Ctrl+X 剪切 裁掉不要的文本
Ctrl+C 拷贝 复制文字
Ctrl+v 粘贴 从剪切板粘贴文字,可以配合win+V
Ctrl+N 创建一个同级界面 比如再开一个浏览器,文档之类的
Ctrl+W 快速关闭当前界面 对于浏览器就是当前标签页,对于应用就是关掉应用
Ctrl+Z 撤销操作 多用于编辑器或者文件管理器
Ctrl+Y 恢复操作 恢复撤销过头的操作
Ctrl+Shift+T 恢复被关闭的网页 有时可能关错了网页
Ctrl+Shift+Esc 打开任务管理器 强制停止某个卡住的应用运行
Alt+一类
快捷键 效果 用途
Alt+F4 关闭当前应用 甚至还可以关机
Alt+Enter 查看文件属性 先用tab选中文件
Alt+Tab 切换应用视图 频繁在两个应用中切换非常好用

Linux Desk

Windows Terminal

常规
命令 作用
dir /b 查看当前目录所有文件
dir /s myfile 在当前目录所有文件查找myfile
cd ./desk/myfile
jupyter notebook
打开jupyter,在网页上写python脚本

Linux Terminal

Git

VsCode

Background

matlab给我们提供了plot,ezplot,fplot,polar,bar,bar3,plot3,mesh,surf一系列绘图的办法,python也给我们matplotlib.pyplot库可以画各种各样的静态图形,可我们有的时候想展示曲线的运动情况,像放动画一样展现出来,甚至还想保存为gif或者mp4之类的文件,这就不得不提到我们今天的主题了:动画实验;

Content

matlab绘图基本算法

不像matplotlib中可以调用animation模块,matlab只能调用绘图的api来实现逐帧绘制;

绘制的基本思想是:

  1. 确定动画的画布;
  2. 确定动画的帧数;
  3. 清空当前的图形;
  4. 绘制当前帧的图形;
  5. 暂停一小会以免动画太快;

有了这些思想,在matlab就可以绘图了,不过想要利用python的库,还需要一些基本知识;

FuncAnimation基础介绍

animation 有个核心类: FuncAnimation ;

FuncAnimation(fig, func, frames, init_func, interval, blit)

  • fig: 绘制动图的画布名称

    这个参数通常由先前的figure()函数创建;

  • func: 回调函数

    更新新一帧的方式,这个函数返回当前帧的绘制对象,请注意返回值不只一个

    一般计算出新的坐标后,利用绘制对象的set_data方法去更新它;

  • frames: 动画的帧数

    参数常见值为n:int,相当于range(n),但事实上也可以取值 iterable,generator,None

  • init_func: 初始帧

    func类似,返回初始帧的绘制对象。

  • interval: 帧长

    决定帧更新频率,单位:ms

  • blit: 选择更新所有点,还是仅更新产生变化的点。

通过这些参数可以看到,基本和matlab手动实现所需要的准备工作是差不多的;

保存动图文件

在matlab中,一般将动画保存到.avi文件中,这是由matlab提供的接口决定的,一般方法如下:

  1. obj=VidioWriter('test.avi'):产生VidioWriter对象,同时起一个名字
  2. open(obj):打开obj对象;
  3. writeVidio(obj,frame):将当前帧存到obj中;
  4. close(obj):关闭obj对象

而在python中,你只需要安装一些依赖项即可,如果用 FuncAnimation 生成的动图,注意参数fps–frames per second:

  • mp4:执行 pip install ffmpeg
  • gif : 执行 pip install Wand
1
2
ani.save("test.mp4", fps=20, writer="ffmpeg")
ani.save("test.gif", fps=50, writer="imagemagick")

Example

实现正方形旋转,保存文件;

我们知道,对于列向量$(x_0,y_0)^T$,逆时针旋转$\theta$角,得到新的向量$(x_1,y_1)^T=\begin{pmatrix}cos\theta&-sin\theta\sin\theta&cos\theta \end{pmatrix}(x_0,y_0)^T$,我们分别采用两种语言实现:

matlab:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
P=[0 1 1 0 0;0 0 1 1 0];
obj = VideoWriter('test.avi');
open(obj);
for t = linspace(0, 3*pi/4, 100)
M = [cos(t) -sin(t);sin(t) cos(t)];
PP = M*P;
plot(PP(1,:),PP(2,:),'r');
axis equal;
axis([-2 2 -2 2]);
frame = getframe(gcf);
writeVideo(obj, frame);
pause(0.05);
end
close(obj);

来看一下我们的test.avi(突然发现它在Typora里预览不了…)

python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import numpy as np 
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation

fig = plt.figure(figsize = (6, 6))
ax = fig.add_subplot(1, 1, 1)
p = np.array([[0,1,1,0,0],[0,0,1,1,0]])
square, = ax.plot(p[0], p[1], color = 'red', animated=True)
frames = np.linspace(0, 3*np.pi/4, 100)

def init():
ax.set_xlim(-2, 2)
ax.set_ylim(-2, 2)
return square,

def update(t):
M = np.array([[np.cos(t), -np.sin(t)],[np.sin(t), np.cos(t)]])
pp = M @ p
ax.set_aspect('equal')
square.set_data(pp[0], pp[1])
return square,

ani = FuncAnimation(fig, update, frames=frames, init_func=init, interval=50, blit=True)
# plt.show()
ani.save("test.gif", fps=25, writer="imagemagick")

test

Remark

又水了一篇…

Background

和动画实验一样,这次也是用matlab和python共同实现,完成对Taylor中值定理,Euler公式,Fourier公式的验证;

这次我们需要的python库:sympy,这个库能让我们像matlab一样完成符号运算;

Content

Taylor公式

先给出Taylor中值定理:

若$f(x)$在$x_0$的临域$U(x_0)$具有直到$n+1$阶导数,则当在$(a,b)$内,$f(x)$可以表示为关于$x-x_0$的$n$次多项式$P(x)$与一个余项$R_n(x)$之和:
$$
f(x)=P(x)+R_n(x)=\sum_{k=0}^{n}\frac{f^{k}(x_0)}{k!}(x-x_0)^k+R_n(x)
$$

$$
R(n)=\frac{f^{n+1}(\epsilon)}{(n+1)!}(x-x_0)^{n+1},\epsilon \text{在}x_0,x\text{之间}
$$

在matlab中利用taylor函数可以直接求出对应展开阶数的P(x)taylor函数的接口如下:

T = taylor(f,var,a)

f是即将展开的函数;

var指定要展开的自变量;

a指定拓展点,也就是说T展开应该是关于(x-a)的多项式;

T = taylor(___,Name,Value)

NameValue是在此之上的选项,例如,可以指定泰勒级数的扩展点、截断顺序或顺序模式扩张。

'ExpansionPoint',x0,指定拓展点为x0

order,n指定展开阶数

下面是对$sin(x)=x-\frac{x^3}{6}+…+(-1)^{\frac{n-1}{2}}\frac{x^n}{n!}+o(x^n)$的展开实验代码

matlab:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
syms x
fx = sin(x);
x0 = 0; %展开点
n=[11 14 17];
for i=1:length(n) %展开阶数: n-1阶
hx(i) = taylor(fx,x,'order',n(i),'ExpansionPoint',x0)
end
xp = linspace(-6,6,400); %创建节点数组
y = subs(fx, x, xp); %通过subs替换符号计算函数值
y1 = subs(hx(1), x, xp); y4 = subs(hx(2), x, xp);
y6 = subs(hx(3), x, xp);
h=plot(xp,y,'r',xp,y1,'k',xp,y4,'b',xp,y6,'c','linewidth',2)
legend(h,'source','n=11','n=14','n=17')
set(gca,'fontsize',16)

通过matlab拟合出来的图像是这样的:

taylorimg

python:

这里需要注意的小点是:利用sympy中的series方法得到的talor展开是带$O(x^N)$的符号式,记得需要用removeO方法去掉,同时将sympy的公式用lambdify转化成numpy的公式才能对linspace计算函数值;

sympyseries方法的接口如下:

expr.series() 方法来对表达式进行级数展开。下面是一些参数:

x: 展开的变量。

x0: (可选)展开点,默认为$ 0$,也就是在 $x=0$ 处展开。

n: (可选)展开式的阶数,就是说要展开到$x-x_0$的几次方。

dir: (可选)展开方向,+ 表示正方向,- 表示负方向(对劳伦展开有用)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import numpy as np 
import sympy
import matplotlib.pyplot as plt

x = sympy.Symbol('x')
y = sympy.sin(x)
n = [11, 14, 17]
val = []
cor = ['r', 'k', 'b', 'c']
xp = np.linspace(-6, 6, 400)
funco = sympy.lambdify(x, y, 'numpy')
yo = funco(xp)
val.append(yo)

for i in range(len(n)):
fi = y.series(x, 0, n[i]).removeO()
funci = sympy.lambdify(x, fi, 'numpy')
yi = funci(xp)
val.append(yi)

fig = plt.figure()
ax = fig.add_subplot(1, 1, 1)
for i in range(len(val)):
ax.plot(xp, val[i], color = cor[i])
plt.show()

最后拟合出来的效果是这样的:

sintaloy

Euler公式

有了Taylor展开的基础后,我们顺便验证Euler公式:$e^{i\theta}=cos\theta + isin\theta$​,使用numpy中的复数,对$(-\pi,\pi)$中一系列点,计算两边值是否相等即可;

1
2
3
4
5
6
7
8
9
10
import numpy as np 
from numpy import cos,sin,pi,e
import sympy

xp = np.linspace(-np.pi, np.pi, 100)
lrh = e**(1j*xp)
rlh = cos(xp)+1j*sin(xp)
if sum(lrh == rlh)==len(xp):
z = sympy.Symbol('z', real = True)
print(sympy.expand(sympy.E**(sympy.I*z), complex = True))

展开的结果确实是

1
I*sin(z) + cos(z)

注意Euler公式有一个常见的变形:
$$
cos\ x=\frac{e^{ix}+e^{-ix}}{2},sin\ x= \frac{e^{ix}-e^{-ix}}{2i}
$$

Fourier变换相关

和Fourier变换有许多知识点,比如作者还打算复习之前学过的快速Fourier变换算法,这是一个十分优秀高效的算法,不过在这里只介绍Fourier变换的强大之处,也就是几乎对各种各样的函数的拟合;

注意之前的Taylor展开对函数的拟合其实并不是那么好,基本只能在展开点附近才有比较好的效果,并且Taylor展开本身对函数要求也很高:要求函数在该点具有足够高阶的导数,我们知道许多函数的性质都不是这么好;

先来复习一下Frourier变换
  • 连续函数的正交:

    若定义在$(a,b)$函数$f(x),g(x)$满足$\int_{a}^{b}f(x)g(x)=0$则称两函数$f(x),g(x)$在$(a,b)$正交;

    如果把函数理解成一系列很密集的散点,那么这些散点构成的向量就满足向量正交的概念,不过在函数取密集的散点向量,不一定是正交的,因为函数描述的是连续的性质,不过我们在工程中经常采用这种近似

  • 关键的积分关系:

    • $\int_{-\pi}^{\pi} 1\cdot cos\ nx dx=0(n=1,2,3…)$
    • $\int_{-\pi}^{\pi} 1\cdot sin\ nx dx=0(n=1,2,3…)$
    • $\int_{-\pi}^{\pi} sin\ kx\cdot cos\ nx dx=0(k=1,2,3…,n=1,2,3…)$
    • $\int_{-\pi}^{\pi} cos\ kx\cdot cos\ nx dx=0(k=1,2,3…,n=1,2,3…,k\neq n)$
    • $\int_{-\pi}^{\pi} sin\ kx\cdot sin\ nx dx=0(k=1,2,3…,n=1,2,3…,k\neq n)$
    • $\int_{-\pi}^{\pi} 1dx =2\pi$
    • $\int_{-\pi}^{\pi} sin^2\ kxdx=\pi(k=1,2,3…)$
    • $\int_{-\pi}^{\pi} cos^2\ nxdx=\pi(n=1,2,3…)$​
  • $1,cosx,sinx,cos2x,sin2x…$是一串两两正交的函数列

  • 根据工程实践猜想傅里叶级数公式:

    若周期信号$f(x)$周期为$T$,角频率为$\omega = \frac{2\pi}{T}$,满足Dirichlet条件:

    1. 一个周期内只有有限个第一类间断点
    2. 一个周期内只有有限个极值点

    则可以展开成下列级数:

    $$
    f(x)=\frac{a_0}{2}+\sum_{n=1}^{\infty}a_ncos\ n\omega x+b_nsin\ n\omega x
    $$
    根据上述「关键的积分关系」待定系数求得:

    直流分量:$\frac{a_0}{2}=\frac{1}{T}\int_{-T/2}^{T/2}f(x)dx$

    傅里叶系数:$a_n=\frac{2}{T}\int_{-T/2}^{T/2}{f(x)cos(n\omega x)dx},b_n=\frac{2}{T}\int_{-T/2}^{T/2}{f(x)sin(n\omega x)dx}$​

  • Fourier级数指数形式:

    $f(x)=\sum_{n=0}^{\infty}a_ncos(n\omega x)+b_nsin(n\omega x)=\sum_{n=0}^{\infty}a_n\frac{e^{in\omega x}+e^{-in\omega x}}{2}+b_n\frac{e^{in\omega x}-e^{-in\omega x}}{2i}$

    $=\sum_{n=0}^{\infty}e^{in\omega x}\frac{a_n-ib_n}{2}+e^{-in\omega x}\frac{a_n+ib_n}{2}$$=\sum_{n=0}^{\infty}e^{in\omega x}\frac{\frac{2}{T}\int_{-T/2}^{T/2}{f(x)\frac{e^{in\omega x}+e^{-in\omega x}}{2}dx}-i\frac{2}{T}\int_{-T/2}^{T/2}{f(x)\frac{e^{in\omega x}-e^{-in\omega x}}{2i}dx}}{2}+ e^{-in\omega x}\frac{\frac{2}{T}\int_{-T/2}^{T/2}{f(x)\frac{e^{in\omega x}+e^{-in\omega x}}{2}dx}+i\frac{2}{T}\int_{-T/2}^{T/2}{f(x)\frac{e^{in\omega x}-e^{-in\omega x}}{2i}dx}}{2}$

​ $=\sum_{n=-\infty}^{\infty}F_ne^{in\omega x}$

​ 其中$F_n=\frac{1}{T}\int_{-T/2}^{T/2}f(x)e^{-in\omega x}dx$​

  • 将周期信号$f(t)$​推广成有限时间的非周期信号,也即时域从周期转化为非周期时,频域从离散的转化为连续的:原始的Fourier变换(FT)
    $$
    F(\omega)=\int_{-\infty}^{\infty}f(t)e^{-i\omega x}dx
    $$

    $$
    f(x)=\frac{1}{2\pi}\int_{-\infty}^{\infty}F(\omega)e^{i\omega x}d\omega
    $$

  • 离散时间无限频谱内的Fourier变换(DTFT)

    将连续信号$f(x)$采样,采样时间点间隔为$T_s$,冲击序列为$\delta_s(x)=\sum_{n=-\infty}^{\infty}\delta(x-nT_s)$,取样信号为$f_s(x)=\sum_{n=-\infty}^{\infty}f(x)\delta(x-nT_s)$,其频谱密度为$F_s(\omega)=\int_{-\infty}^{\infty}f_s(x)e^{-i\omega x}dx=\sum_{n=-\infty}^{\infty}\int_{-\infty}^{\infty}f(x)\delta(x-nT_s)e^{-i\omega x}dx$

    $=\sum_{n=-\infty}^{\infty}f(nT_s)e^{-i\omega nT_s}$

  • 离散傅里叶变换(DFT):

    对于数组$f[n](0\le n<N)$,定义$f$由离散傅里叶变换得到$F$,
    $$
    f\xrightarrow[]{DFT}F:F[k]=\sum_{n=0}^{N-1}f(n)e^{-i\frac{2\pi}{N}n\cdot k},k=0,1,…N-1
    $$
    可待定系数证明$F$由离散傅里叶逆变换得到$f$,
    $$
    F\xrightarrow[]{IDFT}f:f[n]=\sum_{k=0}^{N-1}F[k]e^{i\frac{2\pi}{N}k\cdot n},n=0,1,…N-1
    $$
    由于暂时没看懂其中的物理意义所以留个坑,貌似这样的式子都是天才一眼看出来的🤣,同时给FFT埋个坑

经过简单的对Fourier变换的复习之后,我们来看看我们的任务:

给以$2\pi$为周期的周期函数$f(x)$在区间定义如下,验证傅里叶级数对其近似效果:
$$
f(x)=\begin{cases}
x^2&-\pi\le x<0\
0&0\le x<\pi
\end{cases}
$$
先看matlab代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
T=2*pi;
fx=@(x) (mod(x+pi,T)<pi).*(T-mod(x,T)).^2;
test=4;
xp=linspace(-2*pi,2*pi,1000);
N=[2,4,8,16];
col=['red','cyan','blue','yellow'];
idx=2;
yp=fx(xp);
plot(xp,yp,'color','red','LineWidth',2,'DisplayName','OriginSignal')
hold on
yp_test=[];
for i=1:test
n=N(i);
[fs,an,bn]=FourierSeries(fx,x,n);
yp_t=subs(fs,x,xp);
yp_t=double(yp_t);
yp_test=[yp_test;[yp_t]];
end
plot(xp,yp_test(1,:),'color','green','LineWidth',2,'DisplayName','n=2');
hold on;
plot(xp,yp_test(2,:),'color','cyan','LineWidth',2,'DisplayName','n=4');
hold on
plot(xp,yp_test(3,:),'color','yellow','LineWidth',2,'DisplayName','n=8');
hold on;
plot(xp,yp_test(4,:),'color','blue','LineWidth',2,'DisplayName','n=16');
hold on;
legend('show','location', 'northeast');
hold off

function [fs,an,bn]=FourierSeries(fx,x,n,l,r)
%fx为周期信号
%x为自变量
%n为展开阶数
%[l,r]为周期区间
%an,bn为余弦项系数,正弦项系数
%fs为展开表达式
if nargin==3
l=-pi;
r=pi;
end
T=r-l;
w=2*pi/T;
%fx=subs(fx,x,x+l+T/2);
fx=@(x)fx(x+l+T/2);
an=integral(fx,-T/2,T/2)/T;
bn=[];
fs=an;
for k=1:n
ak=integral(@(x) fx(x).*cos(k*w*x),-T/2,T/2)*2/T;
bk=integral(@(x) fx(x).*sin(k*w*x),-T/2,T/2)*2/T;
an=[an,ak];
bn=[bn,bk];
fs=fs+ak*cos(k*w*x)+bk*sin(k*w*x);
end
fs=subs(fs,x,x-l-T/2);
end

最后拟合出来的效果是这样的,可以看到随着展开阶数增大,拟合效果越来越好,但也可以看到吉布斯现象也越来越显著;

Fourier

用python也可以做到同样的效果,很遗憾python库里也没有直接计算傅里叶级数的函数;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import numpy as np
import matplotlib.pyplot as plt
from scipy.integrate import quad

# Define the original signal function fx
T = 2 * np.pi
def fx(x):
return (np.mod(x + np.pi, T) < np.pi) * (T - np.mod(x, T)) ** 2

# Fourier series calculation
def fourier_series(fx, x, n, l=-np.pi, r=np.pi):
T = r - l
w = 2 * np.pi / T
fs = 0
an = [] # Cosine coefficients
bn = [] # Sine coefficients

# Calculate a0 coefficient
a0, _ = quad(lambda x: fx(x), -T/2, T/2)
an.append(a0 / T)
fs += an[0] / 2

# Calculate remaining an and bn coefficients
for k in range(1, n + 1):
ak, _ = quad(lambda x: fx(x) * np.cos(k * w * x), -T/2, T/2)
bk, _ = quad(lambda x: fx(x) * np.sin(k * w * x), -T/2, T/2)
an.append(ak * 2 / T)
bn.append(bk * 2 / T)
fs += an[k] * np.cos(k * w * x) + bn[k] * np.sin(k * w * x)

return fs, an, bn

# Define the range of x and the number of Fourier series terms
test = 4
xp = np.linspace(-2*np.pi, 2*np.pi, 1000)
N = [2, 4, 8, 16]
colors = ['green', 'cyan', 'yellow', 'blue']

# Plot the original signal
yp = fx(xp)
plt.plot(xp, yp, color='red', linewidth=2, label='OriginSignal')

# Plot the Fourier approximations
for idx, n in enumerate(N):
fs, _, _ = fourier_series(fx, xp, n)
plt.plot(xp, fs, color=colors[idx], linewidth=2, label=f'n={n}')

# Show the legend and plot
plt.legend(loc='northeast')
plt.show()

Reamrk

留坑:

  • 快速傅里叶变换(FFT)和Cooley-Tukey 算法
  • 二维傅里叶变换
  • python画CG

Matlab数学实验学习笔记

MATLAB语言的基本语法

变量名的命名规则

  • 必须以字母开头
  • 区分大小写,可由字母、数字、下划线组成(变量名尽量反映其含义)

赋值语句

基本语法 变量名=表达式

1
2
3
4
5
a=[2 5 6 7 9];

a(2)=10

a=sin(pi/3), [v1,v2,v3]=fun(m1,m2)

表达式语句

一个语句可以只有表达式
系统自动将表达式的结果赋值给MATLAB内部变量”ans”。

语句的分隔符

  • 语句分隔符: 分号或逗号;

  • 语句的末尾不使用分号时,系统会显示执行结果。

    1
    a=3; b=4, c=a^2; a(1,4)=b

常用命令、快捷键

  • who 列出当前工作空间所有变量名称
  • whos 列出当前工作空间变量更多信息(维数,占用内存字节数等)
  • clc 清除命令窗口内容
  • clear 清除工作空间中的变量
  • 快捷键:向上方向键、向下方向键,用于浏览命令窗口历史命令、语句

数组的使用

  • 使用方括号

    同一行的元素用“空格或逗号”分隔,不同行的元素用“分号或换行”分隔

    1
    2
    3
    4
    5
    6
    x=[1 3 5 6 4]
    y=[1, 3, 5, 6, 4]
    A=[1 2 3; 4 5 6; 7 8 9];
    B=[ 1 2 3
    4 5 6
    7 8 9];
  • 冒号操作符

    用于创建行向量 a:step:b ;
    其中a:b等同于a:1:b;

    a起始值,step增量,b用于判断向量终点值.

    1
    2
    3
    x=1:5      %表示x=[1 2 3 4 5],增量默认为1
    x=1:2:9 %表示x=[1 3 5 7 9]
    x=10:-2:1 %表示x=[10 8 6 4 2]
  • linspace(a,b,n)

    n-1等分区间[a, b]的节点组成的行向量(含区间端点a, b);

    注意:如果要产生一个区间上的均匀节点,并且指定所产生数组的元素个数,则使用linspace更为方便。

    不指定n默认100个;

    1
    x=linspace(-2, 2, 5) %表示x=[-2 -1 0 1 2]
  • 拼接

    1
    2
    C=[A B]  %横向拼接要求A,B行数相同
    D=[A; B] %纵向拼接,要求A,B列数相同.
  • 空矩阵 [ ] 产生一个空矩阵

  • 调用函数创建

    1
    2
    3
    4
    5
    6
    7
    8
    a1 = zeros(m, n) 
    b1 = zeros(m)

    a2 = ones(m, n)
    b2 = ones(m)

    a3 = eye(m, n)
    b3 = eye(m)
  • 提取和修改数组中的元素

    • 通过数组下标访问:

      • ≥1的整数;
      • 不能越界
    • 获取子阵:
      获取第r行 A(r, :)
      获取第c列 A(:, c)
      获取子阵 A(行下标向量,列下标向量)
      示例:

      1
      2
      3
      4
      x=[1 2 3 4 5; 6 7 8 9 10;11 12 13 14 15] %创建矩阵
      y1=x([1, 2], :) % 取第1,2行
      y2=x([2 3],[1 3 4]) % 取第2,3行,第1,3,4列
      y3=x([1 3 4]) % 取第1,3,4个数,列优先编号,[1 11 2]
    • 修改元素:用赋值语句修改;

  • 删除数组元素操作
    将空矩阵赋值给相应子阵达到删除;

    1
    2
    3
    4
    5
    6
    7
    8
    x=[1 5 9; 
    2 6 10;
    3 7 11;
    4 8 12] %创建4行3列矩阵x
    y=x([1 3 4],[2 3]) % 取第1,3,4行,第 2,3列赋值给y
    z =x([1 3 5]) %取x第1,3,5个元素赋值给z
    x([1 2],:) = [ ] % 删除x的第1、2行

  • end用法
    end在下标表达式中表示最后一个下标值;

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    x=[1  5  9; 2  6  10; 3 7 11; 4 8 12];  
    x(end,2)= 0; x%将矩阵x的最后一行第2列元素赋值为0

    t = rand(1,10);
    x1 = t(1:end-1) %取第1个-倒数第2个
    x2 = t(end-2:end)%取倒数第3个-倒数第1个

    A = rand(3)
    B = A(1:end-1, : )%取A的第1行-倒数第2行
    C = A(:, [2:end]) %取A的第2列-倒数第1列

算术运算符:矩阵操作运算符

  • 矩阵转置 B.'B' 矩阵共轭转置 $B^{T}$

  • 矩阵加减:A+B,A-B,($A,B$同型,或有一个为标量

  • 矩阵相乘:A * B, $A$与$B$为矩阵或有一个为标量*

  • 矩阵左除:A\B, 当$A$为方阵表示: $A^{-1} B$

  • 矩阵右除:A/B, 当$B$为方阵表示 $AB^{-1}$ ,或$B$为标量

  • 矩阵幂: A^n,$ A$为方阵\

  • inv函数:inv(A) 求$A$的逆矩阵$A^{-1}$

    1
    2
    3
    4
    5
    6
    A = rand(3,3);   
    B = rand(3,3);
    C1 = A\B;
    C2 = A/B
    E1 = C1-inv(A)*B %inv函数求矩阵的逆
    E2 = C2-A*inv(B) %E1,E2 理论上为零矩阵

数组对应元素操作运算符

  • 数组相乘:C=A.*B

  • 数组右除:C=A./B;

  • 数组左除:C=A.\B

  • 数组幂:C=A.^B(要求:A, B同维数或其中之一为标量)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    A=rand(3,4);
    B=rand(3,4);
    A.*B %两个矩阵对应元素相乘
    A./B %两个矩阵对应元素相除(a(i,;,j)/b(i,:,j))
    A.\B %两个矩阵对应元素相除(b(i,;,j)/a(i,:,j))
    A.^B %两个矩阵对应元素幂运算(a(i,;,j)^b(i,:,j))
    T1=A.*2; % 以A的每个元素与2相乘构造数组
    T2=A.^2; % 以A的每个元素2次方构造数组
    T3=2./A; % 以A的每个元素的倒数乘以2构造数组
    T4=2.\A; % 以2的倒数乘以A的每个元素构造数组

算术运算符:标量之间的运算符

标量加减乘除:+ - * / \ ^

逻辑运算符:& | ~

1
2
3
4
5
6
7
8
9
10
11
12
x =[4     9     1     2     1];
y =[1 8 5 5 1];
t1=x>=2 % t1 = 1 1 0 1 0
u=x-y % u = 3 1 -4 -3 0
t2=x-y>=1 %t2 = 1 1 0 0 0

a=3; b=7;
if a>3 & b>3,
disp('handle 1')
else
disp('handle 2')%输出
end

数据类型

主要的数据类型:double char sym struct cell

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
a=rand(3); b='Li San';   %double型,char型
symsx, y=1 + x^2 %x,y为sym类型;对y赋值的语句含符号对象
F.name='li San', F.birth=1999, F.src=rand(3) %F为struct型
whos a b x y F
class(a) % 'double'
class(b) % 'char'
%whos结果
Name Size Bytes Class Attributes

F 1x1 620 struct

a 3x3 72 double

b 1x6 12 char

x 1x1 112 sym

y 1x1 112 sym

cell数组基本用法

  • 创建数组用法:a=cell(m,n)

  • 特点:一个cell数组中的元素的类型可以互不相同

  • 存取cell数组用法示例:

    1
    2
    3
    4
    5
    a=cell(2,3)
    a{1,1}='abc';a{1,2}=rand(3);a{1,3}=cell(1,2);

    % a = 'abc' [3x3 double] {1x2 cell}
    % [] [] []

基本输入与格式化输出操作函数

  • input键盘输入函数

    • input(提示信息字符数组)

      1
      2
      3
      g=input('输入您的成绩: ')
      %输入您的成绩: 95
      %g = 95
  • disp 显示数组内容函数
    特点:显示数组内容,但不输出变量名,多用于调试程序时显示数组内容

    示例:

    1
    2
    a=rand(1,3);
    disp(a)
  • sprintf 将数组内容格式化为字符串

    功能:将数据格式化输出为字符串

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    a =[pi,sqrt(2)];
    name='Li San';
    grade=[86 95 89];
    s1= sprintf('%0.5f',pi) %将该实数化为5个小数位字符串
    s2= sprintf('%10.6f', a) %将a化为10个字符长,含6个小数位的字符串
    s3=sprintf('%8s%3d%3d%3d',name,grade)

    %运行结果:
    s1 = 3.14159
    s2 = 3.141593 1.414214
    s3 = Li San 86 95 89

Matlab中的常用函数

eval将字符串转化为Matlab语句执行

1
2
3
4
for i=1:20
eval(sprintf('syms x%d',i))
end
whos

length获取向量长度函数

s=length(v) 获取向量长度s

sum求和函数

  • s=sum(v) 求向量v中元素的和
  • s=sum(A,1) s=sum(A) 求矩阵A中每列的和,返回成1个行向量
  • s=sum(A,2) 求矩阵A中每行的和,返回成1个列向量
1
2
3
4
5
6
7
8
9
10
11
12
13
a= fix(1000*rand(3,5))/1000;
s=sum(a), s2=sum(a,1) % s, s2完全相同
t =sum(a’,1)
t2= sum(a,2) % t,t2元素值相同,差别在于行/列向量

%运行输出:
s = 1.00700 0.34800 2.46700 0.87400 1.97500
s2 = 1.00700 0.34800 2.46700 0.87400 1.97500
t = 1.8430 2.2620 2.5660
t2 = 1.8430
2.2620
2.5660

mean求平均值函数

  • s=mean(v) 求向量v中元素的平均值
  • s=mean(A,1) s=mean(A) 求矩阵A中每列的平均值,返回成1个行向量
  • s=mean(A,2) 求矩阵A中每行的平均值,返回成1个列向量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
X= [1 2 3; 3 3 6; 4 6 8; 4 7 7]
v1=mean(X,1)
v2=mean(X,2)

%运行输出:
X = 1 2 3
3 3 6
4 6 8
4 7 7
v1 = 3.0000 4.5000 6.0000
v2 =
2
4
6
6

max求最大值函数

[v, I]=max(x)

  • 如果x为向量,v为向量中的最大元素;I为最大元素在x中的下标。
  • 如果x为矩阵,v为每列的最大元素组成的行向量,I则为每列最大元素的行下标组成的向量。

min求最小值函数

[v, I]=min(x)

  • 如果x为向量,v为向量中的最小元素;I为最小元素在x中的下标。
  • 如果x为矩阵,v为每列的最小元素组成的行向量,I则为每列最小元素的行下标组成的向量。

sort排序函数

  • [B, I]=sort(v) 对向量v中元素排序;
    B为按递增排序后的元素;
    I为排序后数组B中的元素在原数组v中的位置下标.
  • 当v是矩阵时,sort(v)或sort(v,1)对列分别排序,
    sort(v,2)对行分别排序。
1
2
3
4
5
6
7
a=[1 5 6 7 4 9]
v=sort(a) % v =1 4 5 6 7 9
[v2,idx2]=sort(a) % v2=1 4 5 6 7 9
%idx2=1 5 2 3 4 6
v_byidx = a(idx2) %v_byidx = 1 4 5 6 7 9
v1_c=sort(a, 'ascend') %升序排列
v2_c=sort(a, 'descend')%降序排列

find查找函数

find函数用于查找数组中的非零元素位置,结合逻辑表达式可以返回所需要元素的位置下标.

1
2
3
4
5
6
a=[1 5 6 7 4 9];
idx=find(a>=6) % idx = 3 4 6

x =[1 9 1 7 8];
y =[8 0 3 2 8];
s = sum((x>=y-2) & (x<=y+2) )%s= 2

Matlab函数文件

函数名命名规范

  • 必须以字母开头,区分大小写,函数名可由字母、数字、下划线组成
  • 保存函数的文件名一般与程序中定义的函数名相同;否则,调用该函数时以保存函数的文件名作为函数名来调用;
  • 函数名要有一定实际含义,便于记忆,同时避免与系统内部函数名相同。
1
2
3
4
5
6
function r=sumbetween(a,b)
%sumbetween.m任意自然数a和b之间(含a和b)所有整数的和
if a <= b,
r =(b-a+1)*(a+b)/2;
else r =(a-b+1)*(a+b)/2;
end

nargin,nargout,return和pause

  • narginnargout分别表示函数调用时的输入参数个数,输出参数个数。
  • return 返回调用函数
  • pause 暂停运行,按任意键执行
  • pause(n) 暂停n秒,如pause(0.5)

inline函数和匿名函数

inline函数根据expr建立内联函数,函数自变量符号根据表达式自动确定;

1
2
3
4
f1 = inline('t^2')   % 系统自动确定参数
f2 = inline('x*y*z') % 系统自动确定参数
f3 = inline('x*y*z','x','y','z') % 指定参数
f4 = inline(‘x^P1+x^P2’,2) % 指定参数x,P1,P2

匿名函数使用@符号:@(参数列表)(函数表达式),返回与输入参数同维数的数组。

1
2
3
4
f=@(x,y)((x.^2+y.^2<=1).*(x+y)+(x.^2+y.^2>1).*(x-y));
x=-2:0.1:2;
y=-2:0.1:2;
v=f(x,y);

MATLAB 一元函数绘图方法

  • plot() 基本绘图方法,利用一元函数自变量的一系列数据和对应函数值数据绘图。具有很大灵活性;
  • ezplot()简易函数绘图方法,优点:快速方便
  • fplot() 函数绘图方法,与ezplot相似.(不同版本要求不同,2019版不能给出函数值变化范围)
  • polar() 极坐标绘图命令
  • bar() 绘条形图命令
  • bar3() 三维条形图绘制命令
1
2
3
4
5
6
7
8
9
plot(x,y) 
plot(x,y,'r-')
plot(x1,y1,x2,y2)
plot(x1,y1,'r',x2,y2,'b')
ezplot(f,[xmin,xmax,ymin,ymax])
fplot(f,[xmin,xmax])
polar(theta,rho,'r.')
bar(x,y)
bar3(x,y)
  • legend在图形上生成一个图例框
  • title在图形顶部添加标题
  • xlabel用字符串标注x轴
  • ylabel用字符串标注y轴
  • gca返回当前图形坐标区坐标轴句柄
  • gcf返回当前图窗句柄
  • subplot另开一个绘图窗口

实例

1
2
3
4
x=0:0.1:4*pi; 
y= exp(-0.5*x) ; y1=y .*sin(5*x);
plot(x,y1,x,y,'--r',x,-y,'--r')
legend('exp(-0.5x)sin(5x)','exp(-0.5x)')
1
2
3
4
5
6
x=linspace(0,2*pi,30);
y=sin(x);
z=cos(x);
plot(x,y,x,z)
legend('sin(x)','cos(x)')
title('Figure: Legend Example')
1
2
3
4
h=ezplot('exp(-0.5*x)*sin(5*x)',  [0,10,-1,1])
set(h, 'linewidth', 2, 'color', 'r')
set(gca,'fontsize', 14, 'fontname', '宋体')
set(gcf, 'color', 'c')
1
2
3
theta=0:pi/20:4*pi;
rho= 1 + theta*2;
polar(theta,rho,'r') %r =1+2θ
1
2
3
4
5
6
7
8
x=-2.9:0.2:2.9;
y= exp(-x.*x);
subplot(1,2,1)
bar(x,y)
title('Figure:2-D Bar Chart')
subplot(1,2,2)
bar3(x,y)
title('Figrure:3-D Bar Chart')

MATLAB 二元函数绘图方法

  • 空间曲线绘制plot3

    1
    2
    3
    4
    5
    6
    t=linspace(0,10*pi);
    plot3(sin(t),cos(t),t)
    xlabel('sin(t)')
    ylabel('cos(t)')
    zlabel('t')
    title('Figure: helix')
  • 生成平面网格点命令: [X, Y]=meshgrid(x, y)

    1
    2
    3
    x=1:6; y=1:8;       %创建两个向量
    [X,Y]=meshgrid(x,y)%将x和y分别扩充为8行6列
    [X,Y]=meshgrid(1:6,1:8)%直接创建两个矩阵X和Y
  • 绘网格命令:mesh(x,y,z)mesh(z)

    1
    2
    3
    4
    [x,y]=meshgrid(-2:0.2:2);
    z=x.*exp(-x.^2-y.^2);
    mesh(x,y,z)
    colormap([0 0 1])

    绘网格命令 meshc() meshz()

    1
    2
    3
    4
    5
    6
    7
    8
    [x,y]=meshgrid(-2:0.2:2);
    z=x.*exp(-x.^2-y.^2);
    subplot(1,2,1)
    meshc(x,y,z)
    title('Figure 1:mesh plot with Contours')
    subplot(1,2,2)
    meshz(x,y,z)
    title('Figure 2:mesh plot with Zero Plan')
  • 等高线图contourcountour3

    1
    2
    3
    4
    5
    6
    7
    8
    [x,y]=meshgrid(-2:0.2:2);
    z=x.*exp(-x.^2-y.^2);
    subplot(1,2,1)
    contour(x,y,z,20)
    title('Figure 1: 2-D Contour Plot')
    subplot(1,2,2)
    contour3(x,y,z,20)
    title('Figure 2: 3-D Contour Plot')

Matlab中的字符串

char(S1,S2,…) 利用给定的字符串或单元数组创建字符数组
double(S) 将字符串转化成ASC码形式
cellstr(S) 利用给定的字符串数组创建字符串单元数组
blanks(n) 生成一个由n个空格组成的字符串
deblank(S) 删除尾部的空格
eval(S),evalc(S) 使用MATLAB解释器求字符串表达式的值
ischar(S) 判断是不是字符串数组
iscellstr(C) 判断是不是字符串单元数组
isletter(S) 判断是不是字母
isspace(S) 判断是不是空格
strcat(S1,S2,…) 将多个字符串水平拼接
strvcat(S1,S2,…) 将多个字符串竖直拼接

strcmp(S1,S2) 判断字符串是否相等
strncmp(S1,S2,n) 判断前n个字符串是否相等
strcmpi(S1,S2) 判断字符串是否相等(忽略大小写)
strncmpi(S1,S2,n) 判断前n个字符串是否相等(忽略大小写)
strtrim(S1) 删除结尾的空格
findstr(S1,S2) 查找
strfind(S1,S2) 在S1查找S2
strjust(S1,type) 按照指定的type调整下一个字符串数组
strmatch(S1,S2) 查找要求的字符串下标
strrep(S1,S2,S3) 将字符串S1中出现的S2用S3代替
strtok(S1,D) 查找S1中第一个给定的分隔符之前和之后的字符串
upper(S) 将一个字符串转换成大写
lower(S) 将一个字符串转换成小写

num2str(k) 将数字转换成字符串
int2str(k) 将整数型转换成字符串
mat2str(k) 将矩阵转换为字符串,供eval使用
str2double(S) 将字符串数组转换为数值数组
sprintf(S) 创建含有指定格式的字符串
sscanf(S) 按照指定的控制格式读取字符串

字符串拼接函数:strcat和strvcat

strcat('MAT','LAB')

运行输出:ans = MATLAB
strvcat('MAT',‘MATLAB')

运行输出:ans =
MAT
MATLAB

字符串与数字数组转换函数:str2num和num2str

1
2
3
4
v=([1:0.5:2]*pi)
str=num2str(v)
v2=str2num(str)
err=v2-v

字符串查找函数:findstr和strfind

k=findstr(S1, S2)找到S1和S2两者中较短那个字符串在较长字符串中的位置起始索引号.
k=strfind(S1,pattern)返回pattern在S1中的位置索引号

Matlab文本文件操作

打开文件

在读写文件之前,必须先用fopen函数打开或创建文件,并指定对该文件进行的操
作方式。

fopen函数的调用格式为:fid = fopen(文件名,‘打开方式’)
说明:其中fid用于储存文件句柄值,如果返回的句柄值大于0,则说明文件打开成功。文
件名用字符串形式,表示待打开的数据文件。

打开文件的方式

  • ‘r’只读方式打开文件(默认方式),该文件必须已存在。
  • ‘r+’读写方式打开文件,打开后先读后写。该文件必须已存在。
  • ‘w’打开后写入数据。该文件已存在则更新;不存在则创建。
  • ‘w+’读写方式打开文件。先读后写。该文件已存在则更新;不存在则创建。
  • ‘a’在打开的文件末端添加数据。文件不存在则创建。
  • ‘a+’打开文件后,先读入数据再添加数据。文件不存在则创建。
  • 另外,在这些字符串后添加一个‘t’,如‘rt’或‘wt+’,则将该文件以文本方式打开;如果添加的是‘b’,则以二进制格式打开,这也是fopen函数默认的打开方式。

关闭文件

文件在进行完读、写等操作后,应及时关闭,以免数据丢失。

关闭文件用fclose函数,调用格式为:sta = fclose(fid)
说明:该函数关闭fid所表示的文件。sta表示关闭文件操作的返回代码,若关闭成功,返回0,否则返回-1. 如果要关闭所有已打开的文件用fclose(‘all’)

常见函数

fgets 读取一行,保留换行符
fgetl 读取一行

fprintf将数据按指定格式写入到文本文件中

1
2
3
4
5
6
fid=fopen(‘mytext.txt’,‘wt’);
for i=1:10
fprintf(fid,‘LINE%5d %10.6f\n’,i ,rand);
end
fclose(fid);
edit mytext.txt

Matlab符号变量计算

符号计算函数可以完成准确的推导、计算。如求极限、求导、求积分等。
计算中的符号变量需要先定义再调用符号计算相关函数进行处理。
符号计算部分功能

  • 复合运算、变量代换及化简
  • 线性代数:行列式,特征值等
  • 微积分:求导,求极限,定积分,微分方程的求解等。

定义符号变量syms或sym函数

1
2
3
4
5
syms arg1 arg2 ...
syms arg1 arg2 ... real
syms arg1 arg2 ... positive
syms arg1 arg2 [m, n] %arg1 arg2为m*n阶符号数组
syms f(x1,x2,x3,...) %f是x1, x2, x3, ... 的符号函数

对于函数sym(A)

  • 如果A是字符串,则产生一个符号变量;
  • 如果A是数值标量或数值矩阵,则其转为符号类型。
1
2
3
4
5
6
7
x1=sym(‘x1’) % 产生数组x=sym ('x', [m, n]) 
a=sym(sqrt(200)), v=sym([100 200])

%运行输出: x1 = x1
%a = 10*2^(1/2)
%v=[ 100, 200]

符号表达式中的符号替换

subs函数将符号表达式s中的符号变量用其他符号表达式或数值代替,实现符号的替换,将s表达式中old变量替换为new,其使用格式为:s1=subs(s, old, new)

1
2
3
syms x y z
f=x^2+y^2+z^2
fval=subs(f,[x,y],[1,2])

simplify对表达式进行化简

1
2
3
syms x y
s1 = simplify(cos(x)^2-sin(x)^2) %s1 = cos(2*x)
s2 = simplify(x^3+3*x^2+3*x+1) %s2 = (x + 1)^3

符号计算精度及其数据类型转换

  • double(s) 将符号表达式s转化为双精度数值
  • vpa(s) 计算符号表达式s的数值结果
  • vpa(s,n) 采用n位有效数字计算精度求s的数值结果
  • digits 显示vpa计算结果的有效数字的位数
  • digits(n) 设置vpa计算结果的有效数字的位数
  • char(s) 将符号表达式s转化为字符串

compose复合函数

  • compose(f, g) 返回复合函数f(g(y)),其中f=f(x),g=g(y). x和y分别为findsym(symvar)从f、g中找到的符号变量.
  • compose(f, g, z) 返回复合函数f(g(z)), f=f(x), g=g(y), x,y含义同上一种用法. 最后用指定变量z代替变量y.
  • compose(f, g, x, y, z) 返回复合函数f(g(z)). 将x=g(y)代入f(x)中, 最后用指定的变量z代替变量y
1
2
3
4
syms x y t
f = 1/(1+x);
g = sin(y)^2
h = compose(f,g,x,y,t) %h = 1/(sin(t)^2 + 1)

limit极限函数

  • limit(f,x,a) 计算f(x)当x趋向于a的极限
  • limit(f,x,a,'right') 计算右极限
  • limit(f,x,a,'left') 计算左极限

diff求导计算函数

  • diff(s,v) 求s对自变量v的1阶导数
  • diff(s,v,n) 求s对自变量v的n阶导数 注:v 为指定的符号变量,可以缺省。
1
2
3
4
5
6
7
syms x y
f= x^2*y + 2*x*y + y*y
d1 = diff(f,x,1)
d2 = diff(f,y,1)
%运行结果:
%d1 = 2*y + 2*x*y
%d2 = x^2 + 2*x + 2*y

int符号积分函数

  • s=int(expr, var)以expr表达式中的变量var为积分变量计算不定积分
  • s=int(expr, var, a, b)以expr表达式中的变量var为积分变量计算定积分,积分上下限分别为b和a

symsum级数求和函数

使用格式为: s=symsum(expr,v,a,b)

solve求解方程(组)

直接列出符号变量的方程,注意用==连接

1
2
3
4
5
6
7
8
9
10
11
syms x y a b
s=solve(a*x+b*y==10,a*x-b*y==20,x,y)
sol_x = s.x
sol_y = s.y

%运行结果:
%s =
%x: [1x1 sym]
%y: [1x1 sym]
%sol_x = 15/a
%sol_y = -5/b

dsolve求解微分方程

调用dsolve函数时,应显示指定自变量,用一个
自变量字符组成的字符串作为最后一个参数传
入;

  1. 如果不指定自变量,默认自变量为t
1
2
3
syms y(x)
d1=diff(y,1);
s=dsolve(d1==(50-0.01*y)*y,y(0)==4,x)
1
y=dsolve('Dy=(50-0.01*y)*y','y(0)=4','x')

梯形法求解积分

Q = trapz(X,Y)

对由表格形式定义的函数使用梯形法进行求解积分。

1
2
3
4
5
x=0:pi/100:pi;
y=sin(x);
trapz(x,y)
%ans =
%1.9998

基于变步长Simpso法求积分

q = quad(fun,a,b,tol)

fun 被积函数文件名或函数句柄但必须是数组对应元素操作运算符;

a, b 积分下限,积分上限;

tol 积分精度,缺省默认为10^(-6);

矩形区域二重数值积分

q = dblquad(fun,a,b,c,d,tol)

fun 被积函数文件名或函数句柄

a, b 第一个自变量积分下限,积分上限

c, d 第二个自变量积分下限,积分上限

tol 积分精度

Matlab微积分实验:泰勒展开

  • 实验任务1. 请以函数$f (x)=e^x$为例,验证随着n阶泰勒多项式$Pn(x)$的阶数增加,$Pn(x)$近似函数ex的程度越高。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    syms x
    fx = exp(x);
    x0 = 0; %展开点
    n=[2 5 7];
    for i=1:length(n) %展开阶数: n-1阶
    hx(i) = taylor(fx,x,'order',n(i),'ExpansionPoint',x0)
    end
    xp = linspace(-3,3,40); %创建节点数组
    y = subs(fx, x, xp); %通过subs替换符号计算函数值
    y1 = subs(hx(1), x, xp); y4 = subs(hx(2), x, xp);
    y6 = subs(hx(3), x, xp);
    h=plot(xp,y,'r',xp,y1,'k',xp,y4,'b',xp,y6,'c','linewidth',2)
    legend(h,'source','n=1','n=4','n=6')
    set(gca,'fontsize',16)
  • 实验任务2. 利用指数函数$e^x$的泰勒多项式计算数学常数e的近似值,并绘制误差曲线.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    fac=1; %初始化, 存储各项阶乘值
    n = 5; %设定n,
    s(1) = 2; %求和变量初始化s(n)
    for i= 2:n
    fac = fac*i;%计算i!
    s(i) = s(i-1) + 1/fac;
    end
    err=abs(s-exp(1))
    semilogy(1:n,err,'-o')

Matlab微积分实验:求解非线性方程

  • solve,roots,fzero命令的应用

    1
    2
    syms x
    s=solve((x+2)^x==2, x)

    对于P为按降幂排列的多项式系数, R列向量。

    1
    2
    P=[1 0 0 1];%求方程x3+1=0的根
    R=roots(P)

    fzero的典型调用格式:

    • [x,fval,exitflag]=fzero(fun,x0)
    • [x,fval,exitflag]=fzero(fun,[a,b])
    1
    2
    3
    4
    5
    syms x
    f=2*x^3-3*x^2+4*x-5
    fun=inline((f), 'x')
    x=-5:0.1:10; plot(x, fun(x))
    [x,val,flag]=fzero(fun,2)
  • 二分法及其实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    function [x,n]=bisection(f,a,b,d) 
    %二分法求方程的根:可以是代数方程,也可以是超越方程
    %f是所要求解的函数
    %a,b是求解区间
    %d是求解精度
    %输出x是方程的近似根,n是迭代步数
    fa=f(a);fb=f(b);
    n=1;%计数器初始化
    if fa*fb>0,
    error('所给区间内没有实数解!');
    end
    while 1%未知循环次数,不好用for循环
    c=(a+b)/2;fc=f(c);
    if abs(fc)<d;
    x=c;
    break;
    elseif fa*fc<0,
    b=c;
    fb=fc;
    else
    a=c;
    fa=fc;
    end
    n=n+1;
    end
  • Newton法迭代公式

    image-20240105221822510

image-20240105221935381

Matlab微积分实验:多项式拟合

  • 多项式拟合函数:polyfit( )
    调用格式: p=polyfit(x,y,n)
    说明:x,y为数据点,n为多项式阶数,返回p为幂次从高到低的多项式系数向量p。
  • 多项式求值函数:polyval( )

​ 调用格式: y=polyval(p,x)
​ 说明:为返回对应自变量x在给定系数p的多项式的值。

  • 非线性最小二乘拟合:lsqcurvefit( )

    [c,resnorm,residual,exitflag]=lsqcurvefit(‘fun’, x0, xdata, ydata, lb, ub).

    fun为事先建立的函数F(c, x)的M-文件或匿名函数,;

    x0为迭代初始值;
    lb,ub:解向量的上下界限,lb <= x0 <= ub,若没有要求,就设为空lb=[ ],ub=[];
    c:拟合的最优解;

    resnorm:残差平方和;
    residual:残差向量;

    exitflag: 条件退出标示.

    1
    2
    3
    4
    5
    6
    7
    xdata =[0.9  1.5  13.8  19.8  24.1  28.2  35.2  60.3  74.6 81.3];
    ydata =[455.2 428.6 124.1 67.3 43.2 28.1 13.1 -0.4 -1.3 -1.5];
    fun = @(c,x)c(1)*exp(c(2)*x);
    x0 = [100,-1];
    [c, resnorm, residual, exitflag]= lsqcurvefit(fun, x0, xdata, ydata)
    %要计算q=3:0.4:24的函数值:
    Y=fun(c, q)

Matlab求解规划问题

  • 线性规划问题

    [x, fval] = linprog(c,A,b,Aeq,beq,Lb,Ub)

    image-20240122213537579

    1
    2
    3
    4
    5
    6
    7
    8
    9
    C = [500,600];
    A = [-1,-1;1,0;0,1];
    b = [-5000;5000;3000];
    Aeq = [];
    beq = [];
    Lb = [0;0];
    Ub = [inf;inf];
    x = linprog(-C, A, b, Aeq, beq, Lb, Ub)
    z = C*x
  • 单变量无约束(边界约束)最优化问题

    [xmin, ymin] = fminbnd(fun, x1, x2)

    fun是目标函数

    [x1,x2]是搜索区间

    xmin,ymin分别是目标函数的极小点、极小值。

    如果想求最大值,只需要取相反数即可;

  • 求多变量无约束最优化问题的最优解

    [xmin, fmin] = fminsearch(fun, x0)
    [xmin, fmin] = fminunc(fun, x0)
    fun是目标函数;

    x0是初始迭代点,
    xmin,fmin分别是目标函数的极小点、极小值。
    fminsearch适用范围更广,但处理问题的规模较小,求解速度较慢。fminunc求解更高效。

  • 非线性规划数学模型

    [xmin, fmin] = fmincon(fun,x0,A,b,Aeq,beq,Lb,Ub,nonlcon)

    fun是目标函数

    x0是初始迭代点

    nonlcon是针对非线性约束编写的函数的文件名。

  • 随机优化算法,

    解决困难、复杂、多态最优化问题的全局极小点的有效方法,即优化问题或高维、或不可导、或具有许多局部极小点、或目标函数不具有显式解析表达式等。
    [xmin, fmin] = ga(fun, n, A,b,Aeq,beq,Lb,Ub,nonlcon)
    fun是目标函数

    n是决策变量个数

    nonlcon是针对非线性约束编写的函数的文件名。
    注:随机优化算法,往往需要多次运行程序。

Matlab概率统计应用实验

随机数的生成

rand 生成$(0,1)$区间上均匀分布的随机数
unifrnd 生成指定区间内均匀分布的随机数
randn 生成服从标准正态分布的随机数
normrnd 生成指定均值、标准差的正态分布随机数
exprnd 生成服从指数分布的随机数
注:rand是采用线性同余法得到的,具有周期性,所以上述命令常被称为伪随机数生成器.
rand(‘seed’, number)

接口调用以rand为例:

rand(m) 生成$m\times m$维的随机数
rand(m,n)生成$m\times n$维的随机数
rand([m,n,p ...]) 生成排列成$m\times n \times p…$ 多维向量的随机数

蒙特卡罗方法

利用随机数模拟随机变量,求解一系列诸如面积,体积,值域,(非)线性规划相关问题;举一个例子(估计圆周率):

1
2
3
4
5
6
7
8
9
n=input('请输入产生点的个数:');
m=0;
for i=1:n
x=-1+2*rand; y=-1+2*rand;
if x^2+y^2<=1
m=m+1;
end
end
mypi=4*m/n

快捷键

移动光标

0:移动到行首;
$:移动到行末;
h:左移动一列;
j:下移动一行;
k:上移动一行;
l:右移动一列;

选择文本visual

v:从当前光标选中文本;
V:选中当行;

复制yank

y:复制当前光标选中的文本;
yy:复制当前行;
5yy:复制当前行的接下来5行;

粘贴paste

p:在光标的位置粘贴文本;
5p:在光标位置连续粘贴5次文本;
P:在光标之前粘贴文本;

删除/剪切delete

d:删除光标所在列;
dd:删除光标所在的行;
5dd:删除光标所在的5行;

0%