多元函数隐函数定理

隐函数存在定理

首先考虑 $F:\mathbb{R}^2 \rightarrow \mathbb{R}$ 的最简单情形。

若函数 $F(x,y)$ 在定义域区域 $D$ 内有连续的偏导数 $F_x,F_y$(i.e. $F \in C^1(D)$),且满足如下条件:

  1. $\exists x_0, y_0 \in D, \text{ s.t. } F(x_0, y_0) = 0$(存在零点)
  2. $F_y(x_0, y_0) \neq 0$

则在 $x_0$ 的一个邻域 $U(x_0, \delta)$ 内,存在函数 $y=y(x)$,使得

$$
F(x,y(x)) \equiv 0, \forall x \in U(x_0, \delta).(*)
$$
注:

  • 由该定理的局部性,此处的定义域区域 $D$ 可缩减至 $(x_0, y_0)$ 的某个邻域 $U((x_0, y_0),r)$ 内。
  • 由数学分析的性质可证明,$y(x) \in C^1(x_0-\delta, x_0+\delta)$。
    此时由复合函数的链式法则,可得
    $$
    \frac{\partial F}{\partial x} + \frac{\partial F}{\partial y}\frac{\partial y}{\partial x} = 0
    $$
    特别注意:
  • 此处的 $\cfrac{\partial F}{\partial x}$ 实质上是 $F_1’$,因为有 $\cfrac{\partial F}{\partial x} \equiv 0$ (考虑 $F = F(x)$)。
  • $\cfrac{\partial y}{\partial x} = \cfrac{\mathrm{d} y}{\mathrm{d} x} = f’(x)$ 。
    多元函数部分有严重的记号混用、滥用、异用的情况,后面会尽可能详细说明。

证明从略。
上方的条件 2 实质上是确认因变量唯一性的一种充分性条件。更形象地说,其确认了 $F(x,y)$ 的三维面图象与 $xOy$ 在局部的交集为线。

当扩充到多元多个函数时,可以用线性代数的知识判断出主元关于自由变量的函数。不难猜测,此时给定函数方程的个数在一般下应该等于主元的个数。

设有 $(x_0,y_0,z_0)$ 使得 $F(x_0,y_0,z_0)=0,G(x_0,y_0,z_0)=0$。我们仍然要求函数是 $C^1$ 的。条件 1 显然不再改变,此时我们引入 Jacobi 行列式来陈述条件 2。事实上,记 $J = \cfrac{\mathrm{D}(F,G)}{\mathrm{D}(u,v)}$ 为 F, G 的雅可比行列式,则 $J \ne 0$ 即为条件 2。

$f(x,y)=\cfrac{2xy}{x^2+y^2},f(0,0)=0$

2022 全创作概念辑《湖水》

2022 全创作概念辑《湖水》:整轨分轨并行式首创

“游走于黑白分界,于幻梦再现真实”,如你所见,概念辑《湖水》。

概念辑《湖水》,内容很杂,熔铸了对切近的思考,小到谎言与真挚的搏斗、大到短视与杞人的争执。事情有大有小,篇幅有长有短,道理有的浅显有的隐晦,谜语有的有标答有的不设标答。

有人说,语言是思想的载体。而我则说,语言是思想的源泉。概念辑《湖水》,在文学性上下了一番工夫。

概念辑《湖水》,名字是率性而起,内容则精雕细琢,尽量不赘一字。

概念辑《湖水》,和之前的所有作品一样,在探索中纂成,既是作者的摸索,也是读者的物色。希望它拥有触动人心的力量,使你沉浸在全开放的寻味之旅中,入口回绵。

概念辑《湖水》,Introducing…

整轨:水生

分轨:古船 | 透明的颜色 | 汪洋 | 梁山泊 | 黑夜 | 雪

第三次写雪

好多好多的雪,一片一片的,有大有小。

它们挤在空气里。

有时候风停了,它们盘旋一会儿,便无可抗拒地被拉向地心,覆在枯兀的树枝旁,盖在黑褐色的山丘上。

有时候风大了,它们集结成束,近乎平行地面地飞着。密密麻麻的细丝轻轻颤动,像填满罅隙的琴弦。

它们还是要落在地上,躺在毫无新意的地方。规则的六角形,在触到固体的刹那,便化为了飞灰。它们在严冬的苍白的太阳里升腾,变成交叠的球团,又回到没有棱角的松仁。

我看到临别的雪花,恋恋不舍地吻着空气,像我所奢望的那样。

数论:逆元

什么是逆元?

若 $ax \equiv 1 \pmod b$,则称 $x$ 是 $a$ 关于模 $b$ 的逆元,常记做 $a^{-1}$。

上式等价于 $ax + by = 1$,因此,一种求逆元的方法就是利用扩欧解方程 $ax + by = 1$。

显然,逆元不一定存在:其存在的充要条件为 $(a, b) = 1$。

推论:$p$ 是质数,$p$ 不整除 $a$,则 $a$ 模 $p$ 的逆元存在。

阅读更多

数论:不定方程整数解

欧几里得算法

又称辗转相除法,迭代求两数 gcd。

由 $(a, b) = (a, ka + b)$ 的性质,$\gcd(a, b) = \gcd(b, a\bmod b)$。容易证明这么做的复杂度是 $O(\log n)$。

注意:$\gcd(0, a) = a$。

阅读更多

图论:LCA

LCA: Lowest common ancestor 最近公共祖先

倍增求 LCA

预处理向上跳 $2^k$ 步的结果数组 f[k][x]

求的时候先把两个点跳到一个深度。这里有一个特判,如果重合直接返回这个点。

然后log值从大往小枚举,两个点一起不断向上跳,直至父亲相同,直接返回父节点。

可以 $O(n)$ 预处理log值,把单次查询复杂度降到 $O(常数)$。

复杂度:预处理 $O(n \log n)$,查询 $O(1)$

阅读更多

凝眉

他和她走下车。站台上熙熙攘攘的人守望在那里。没有人向他们看上一眼。

他们停下脚步,看着列车消失在金色的反光里,只留下无底的空白。

“所以……新见和五反田他们呢?”高桥问道。

“他们?他们不会来了。”他想了想道。“他们来过这里。”

她点了点头。

“走吧。”

他握住她的手。


阅读更多

年轻人不讲武德

缘起

健身房的年轻后生不讲武德偷袭马老师,把马保国老师的眼睛给蹭了一下

音译

啊朋友们好啊,我是浑元形意太极门掌门人马保国。

刚才有个朋友,问我马老师发生甚么事了,我说怎么回事,给我发了几张截图。我一看,嗷,原来是左天,有两个年轻人,30多岁,一个体重90多公斤,一个体重80多公斤。塔们说,诶,有一个说是,我在健身房练功,颈椎练坏了,马老师你能不能教教我浑元功法,矮…帮助治疗一下我的颈椎病。我说可以。

阅读更多

图论:Tarjan

前置概念

时间戳:搜索时第几个搜索到这个点。如搜索顺序是1->2->3->6,则6的时间戳为4

对于无向图

连通分量:对于图G来的一个子图中,任意两个点都可以彼此到达,这个子图就被称为图G的连通分量(一个点就是最小的连通分量)

最大连通分量:对于图G的一个子图,这个子图为图G的连通分量,且是图G所有连通分量中包含节点数最多的那个,即为G的最大联通分量

阅读更多

初级动态规划:LIS、LCS、背包

LIS & LCS

P1020 导弹拦截

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
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n = 0;

int a[N], b[N], s[N], ls[N];
void add(int x, int v) {
for(; x<=n; x+=x&(-x)) s[x] = max(s[x], v);
}

int query(int x) {
int ans = 0;
for(; x>0; x-=x&(-x)) ans = max(ans, s[x]);
return ans;
}
int main() {
//freopen("p1020_1.in", "r", stdin);
for(; scanf("%d", a+n+1) != EOF; ++n, b[n] = a[n]);

sort(b+1, b+n+1);
int t = unique(b+1, b+n+1) - (b+1);

for(int i=1; i<=n; ++i)
a[i] = lower_bound(b+1, b+t+1, a[i]) - b;

int ans = 0;
for(int i=n; i>0; --i) {
int q = query(a[i]) + 1;
add(a[i], q);
ans = max(ans, q);
}
printf("%d\n", ans);

ans = 0;
memset(s, 0, sizeof s);
for(int i=1; i<=n; ++i) {
int q = query(a[i]-1) + 1;
add(a[i], q);
ans = max(ans, q);
}
printf("%d\n", ans);
return 0;
}

P1439 【模板】最长公共子序列

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
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

const int N = 100010;

int n, b[N], p1[N], p2[N], s[N];

int lowbit(int x) {
return x&(-x);
}
void add(int x, int v) {
for(; x <= n; x += lowbit(x)) s[x] = max(s[x], v);
}
int query(int x) {
int ans = 0;
for(; x > 0; x -= lowbit(x)) ans = max(ans, s[x]);
return ans;
}
int main() {

scanf("%d", &n);
for(int i=1; i<=n; ++i) scanf("%d", p1+i);
for(int i=1; i<=n; ++i) scanf("%d", p2+i);

for(int i=1; i<=n; ++i) b[p1[i]] = i;
for(int i=1; i<=n; ++i) p2[i] = b[p2[i]];

int ans = 0;
for(int i=1; i<=n; ++i) {
int q = query(p2[i]-1) + 1;
add(p2[i], q);
ans = max(ans, q);
}

printf("%d", ans);
return 0;
}

0-1 背包

$$
F(i,j)=
\begin{cases}
F(i-1,j)& j \leq w_i\\
\max{F(i-1,j),F(i-1,j-w_i)+v_i}& j > w_i
\end{cases}
$$

注意二维转换成一维的时候,$j$ 要从后向前枚举,因为每次的新结果都是根据上一个结果来求得的,从后向前可避免重复取同一物品。

阅读更多